Next: Conclusion Up: Selected Methods for Previous: Using Abduction for

Knowledge Base Verification

It has already been pointed out that only those generalizations and abductive solutions are accepted which are consistent with the integrity constraints IC. Integrity constraints encode negative or disjunctive knowledge. These integrity constraints are represented as denials, i.e. clauses with an empty head. Eshghi and Kowalski use this kind of integrity constraints for their abduction procedure [\protect\citeauthoryearEshghi and Kowalski1989]. We can also represent them as clauses with the special atom false as conclusion [\protect\citeauthoryearManthey and Bry1987].

An obvious integrity constraint is that if a material contains a fluent additive it is no longer pure. This is represented by the following rule: if a material Pl has a fluent additive and the same material is pure then there is an inconsistency:

false additive(Pl,X), pure(Pl)
Consider for example, that the following facts and rules would be contained in a knowledge base.

In Section 5.4 we have found by abduction that Hostalen PPK 1060 could be recycled without any restriction if it was pure. So we can tentatively add this information to the knowledge base as an additional fact: pure(ppk_1060).

A naive method for integrity checking would be to use a proof-finding approach and ask the query

?- false
This procedure would invoke all integrity constraints in backward direction even if they are independent from the new fact. However, it would be much more efficient to derive only those facts that are consequences of this new assertion. In [\protect\citeauthoryearEshghi and Kowalski1989] it is argued to do this kind of constraint checking by forward reasoning starting with the new fact. But forward reasoning from one fact alone is not sufficient. The following integrity constraint says that ``polypropylenes and ABSCs must not be components of a single composite product''.

Adding the new fact composite(ppk_1060, r_5320) would lead to an inconsistency which will not be detected by forward chaining this fact alone. Additionally, we need to prove whether the premises polypropylene(ppk_1060) and absc(r_5320) can be satisfied.

In [\protect\citeauthoryearManthey and Bry1987] a model-generation approach has been applied for this problem. Here, however, we regard checking of integrity constraints as a consequence-finding problem [\protect\citeauthoryearInoue1991]. Given an update of a deductive database or a logic program, consequence finding applies only those rules that are effected by the update operation. This builds on the assumption that the database satisfied its integrity constraints prior to the update. Derivation is restricted to exactly those facts that depend on an explicitly given set of initial facts, in our case the hypotheses found by abduction.

The extended SLDNF resolution of [\protect\citeauthoryearSadri and Kowalski1988] uses the clauses corresponding to the updates as top-clauses for the search space and thus achieves the effect of simplification methods investigated by [\protect\citeauthoryearDecker1986][\protect\citeauthoryearLloyd et al.1987][\protect\citeauthoryearNicolas1982]. The approach combines forward and backward chaining depending on whether a positive or negative literal is resolved upon.

As an alternative to this tuple-oriented method we have developed a rewriting approach [\protect\citeauthoryearHinkelmann1994]. It is an extension of the well-known Generalized Magic Sets rewriting technique [\protect\citeauthoryearBeeri and Ramakrishnan1991], which was also the basis for bottom-up abduction in Section 5.4.1. Since this technique in some sense integrates forward and backward chaining, it seems natural to extend it for consequence finding.

By Generalized Magic Sets rewriting, information about variable bindings given by the query is propagated down into the bodies of the rules at compile-time. For consequence finding we do not have a query but a number of initial facts - the update information - from which to reason forward.

Thus, the input to the consequence finding transformation is a set of initial facts and the rules of the knowledge base. The transformation algorithm specializes the knowledge base by introducing additional rules and predicates. It extends the Generalized Magic Sets rewriting by an up propagation in addition to the usual down propagation. When the rewritten knowledge base is evaluated by a model-generating, bottom-up procedure, the generation of a complete minimal model is restricted to the consequences of the initial facts. Because it is a set-oriented strategy it is very efficient if facts have to be retrieved from a database.



Next: Conclusion Up: Selected Methods for Previous: Using Abduction for


Harold Boley & Stefani Possner (possner@dfki.uni-kl.de)