Query Answering in Circumscription
Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 426-430.
© 1991 International Joint Conferences on Artificial Intelligence
Abstract
We address the problem of answering queries in circumscription and related nonmonotonic formalisms. The answering process we describe uses resolution-based theorem provers recently developed for circumscription. In a way analogous to query answering techniques in classical predicate logic, the process extracts information from a proof of the query. Circumscriptive theorem provers consist of two processes, generating explanations for the theorem to be proved and showing that these explanations cannot be refuted. In general, many explanations compete in supporting the theorem. We show that queries can be answered by finding certain combinations of explanations, and present results to search the space of explanations, while carrying out significant pruning on this space. The results are relevant to other nonmonotonic formalisms having explanation-based proof procedures.
- [Chang and Lee, 1973] Chin-Liang Chang and Richard Char-Tung Lee. Symbolic Logic and Mechanical The- orem Proving. Academic Press , New York, 1973.
- [de Kleer, 1986] Johan de Kleer. An assumption-based TMS. Artificial Intelligence, 28 : 127-162, 1986.
- [Etherington, 1988] David W. Etherington. Reasoning with Incomplete Information. Pitman, London, 1988.
- [Geffner, 1990] Hector Geffner. Causal theories for non- monotonic reasoning. In Proceedings of the 8th AAAI, pages 524-530, Boston, MA, 1990.
- [Gelfond et al., 1989] Michael Gelfond, Halina Przy- musinska, and Teodor Przymusinski. On the relation- ship between circumscription and negation as failure , Artificial Intelligence, 38: 75-94, 1989.
- [Ginsberg, 1989] Matthew L. Ginsberg. A circumscrip- tive theorem prover. Artificial Intelligence, 39: 209- 230, 1989.
- [Green, 1969a] Cordell Green . Theorem-proving by res- olution as a basis for question-answering systems. In : B. Meltzer and D. Michie, editors, Machine Intelli- gence 4, pages 183-205, Edinburgh University Press, Edinburgh, 1969.
- [Green, 1969b] Cordell Green. Application of theorem proving to problem solving. In Proceedings of the IJ- CAI, pages 219-239, Washington D.C ., 1969. IJCAI
- [Inoue and Helft, 1990] Katsumi Inoue and Nicolas Helft . On theorem provers for circumscription. In Pro- ceedings of the 8th Biennial Conference of the Cana- dian Society for Computational Studies of Intelligence , pages 212-219, Ottawa, Ontario, 1990.
- [Inoue, 1991] Katsumi Inoue. Consequence-finding based on ordered linear resolution. In Proceedings of the 12th IJCAI, Sydney, Australia, 1991. IJCAI
- [Lifschitz, 1985] Vladimir Lifschitz. Computing circum- scription . In Proceedings of the 9th I JCAI, pages 121- 127, Los Angeles, CA, 1985.
- [McCarthy, 1986] John McCarthy. Applications of cir- cumscription to formalizing common-sense knowledge. Artificial Intellig ence, 28: 89-116, 1986.
- [Minicozzi and Reiter, 1972] Eliana Minicozzi and Ray- mond Reiter. A note on linear resolution strategies in consequence-finding. Artificil.l Intelligence , 3: 175- 180, 1972.
- [Oxusoff and Rauzy, 1989] Laurent Oxusoff and An- toine Rauzy. L'eva.luation semantique en calcul propo- sitionnel. These de Doctorat , Universite d'Aix- Marseille II, Luminy, France, 1989 .
- [Poole, 1989] David Poole. Explanation and prediction : an architecture for default and abductive rea.'Soning . Comp• utational Int elligen ce , 5: 97-110, 1989 .
- [Przymusinski, 1989] Teodor C. Przymusinski. An algo- rithm to compute circumscription. Artificial Intelli- gence, 38: 49-73, 1989.
- [Reiter and de Kleer, 1987] Raymond Reiter and Johan de Kleer. Foundations of assumption-based truth maintenance systems: preliminary report. In Proceed- ings of the 6th AAAI, pages 183-187, Seattle, WA, 1987.
- [Schlipf, 1986] John S. Schlipf. How uncomputable is general circumscription? In Proceeings of the 1st IEEE Symposium on Logic in Computer Science, pages 92-95, Cambridge, MA, 1986.
- [Siegel, 1987] Pierre Siegel. Representation et utilisa- tion de Ia connaissance en calcul propositionnel. These d'Etat . Universite d'Aix-Marseille II, Luminy, France, 1987.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
For the first-order predicate logic, techniques devel oped by Green [1969a] are the basis for query-answering systems extensively used in deductive databases, logic programming and synthesis problems such as plan ning. These techniques rely on resolution-based theo rem provers that attempt to prove the query while keep ing track of the information generated during the proof. Theorem provers can decide whether a query follows from a given theory, and thus answer questions such as "Is there a coffee cup?"; the corresponding query answering procedure computes the instance for which the query holds and can provide answers to questions such as "Where is the coffee cup?" .
This paper addresses the query answering problem for logic databases augmented with a circumscription axiom [McCarthy, 1986] and related nonmonotonic formalisms. As in the first-order case, the answering procedure we present extracts information from a proof of the query.
·supported by the NTT Corporation, and by the Office of Naval Research under Contract No. N00014-89-C- 0095.

David Poole
Department of Computer Science University of British Columbia Vancouver, B.C. Canada V6T 1W5
We build on existing proof procedures for circumscrip tion that have recently been developed [Przymusinski, 1989; Ginsberg, 1989; Inoue and Helft, 1990] .
While existing theorem provers for circumscription can correctly answer whether or not a formula follows from a circumscription, Green's techniques, although necessary, are not sufficient to provide answer extrac tion. The reason is the following. Circumscriptive theo rem provers are based on finding explanations, or argu ments, for the theorem to be proved, and showing that these explanations cannot be refuted. In general, many explanations compete in supporting the theorem, and a certain combination of these has to be found . We show that to an informative answer corresponds a particular combination of explanations, and present a procedure to find these combinations, together with results to search this space and carry out significant pruning.
Although we focus on circumscription, the results we present obviously apply to its restrictions, as for exam ple logic databases using different types of closed-world assumptions, and similar default reasoning systems hav ing explanation-based proof theories [Geffner , 1990; Poole, 1989].
The next section is a summary of results concerning circumscription and its theorem provers. Section 3 illus trates the problem through an example, and Section 4 provides the main results on extracting answers from a proof.
2 Background
This section gives a very brief survey on circumscription and its proof procedures. Additional background can be found in [McCarthy, 1986; Lifschitz, 1985].
2.1 Circumscription
The circumscription of a first-order theory T is its aug mentation with a second-order axiom CIRC(T; P; Z), where P and Z denote sets of predicate symbols of T, whose model-theoretic characterization is based on the following definition and result.
Definition 2.1 Let M1 and M2 be models ofT. Then M1 <p z M2 if M1 and M2 differ only in the way they intet1>r~t predicates from P and Z, and the extension of every predicate from Pin M1 is a. subset. of its extension in M2 · A model M ofT is (P, Z)-minimal iffor no other model M' ofT it is the case that M' S.P,Z M. 1
The predicates in P are said to be minimized and those in Z to be variables ; Q denotes the rest of the predicates, called parameters.
Theorem 2.2 CIRC(T; P; Z) f= F if and only if M f= F , for every (P, Z)-minimal model M of T . 2
2.2 Theorem Proving Results
General circumscription is highly uncomputable [Schlipf, 1986], and existing theorem proving results apply to restrictions of circumscriptive theories. From now on, T is a first-order theory without equality, consisting of finitely many clauses, each of which is a disjunction of possibly negated atoms called literals, augmented with the Unique Names Assumptions, that is, different ground terms denote different elements of the domain. We also assume that the Domain Closure Assumption is satis fied since this is necessary to guarantee the soundness of the query answering procedure described in this pa per. Queries to be answered are restricted to existen tially quantified formulas (note that this includes ground formulas).
Theorem proving techniques for circumscription are based on the following results [Gelfond et a/., 1989; Przymusinski, 1989; Ginsberg, 1989].
Definition 2.3 Let T be a theory, CIRC(T; P; Z) its circumscription, F a formula, and let p+ (P-) denote the set of positive (negative) literals whose predicate symbol belongs to P .
- p- + Q 3 is called the explanation vocabulary.
- A finite conjunction E of literals from the explana tion vocabulary is an elementary explanation for F relative toT if
- (a) T + E f= F, and
- (b) T + E is consistent .
A disjunction of elementary explanations is called an explanation.
- Let E be an explanation. An elementary explana tion for -.E is called a counter to E .
- If an explanation has no counters it is valid.
- A valid explanation E is minimal if there is no other valid explanation E' such that E' f= E.
Theorem 2.4 CIRC(T; P; Z) f= F if and only if there exist a valid explanation for F relative to the theory T .
Example 2.5 Consider the theory
where P = {ab}, Q ={bird} and Z ={flies}, so that the explanation vocabulary is { ab} - +{bird}+ +{bird}- . Let us consider the query
1 We will often just say minimal models, P and Z being clear from the context.
2 f= is classical first-order.
3 We identify Q with the set of all li terals whose predicate symbols are parameters.
Now, -.ab(tweety) is an explanation for F, as it im plies F together with T and belongs to the explana tion vocabulary. It has no counters, as no formula from the explanation vocabulary can be consistently added to T to deduce ab(tweety). F is thus a theorem of CIRC(T; {ab} ; {flies}) .
Then -.ab(sam) is a counter to -.ab(tw~ety) relative to T' . As no other valid explanation for F exists, F is not a theorem of the circturi'scription ofT'.
2.3 Query Answering Procedure
In line with the above results, the task of a query an swering procedure for circumscription is to search for explanations of the query and test their validity.
To do so, the answering procedure can rely on an explanation-finding algorithm. Such an algorithm is pro vided with a set of clauses T, a clause F, and a vocabu lary, and returns an explanation E, that is, a conjunction of literals from the vocabulary, consistent with T, such that T + E f= F. The computation of explanations is based on the observation that such T, F and E verify
- (b) T~-.E.
Explanations can thus be obtained by computing the set
that belong to the vocabulary p+ +Q. We call these the new theorems of -.F relative to T. 4 The negation of each of such clauses (a conjunction of literals from the expla nation vocabulary) is an elementary explanation and any disjunction of these is an explanation.
Testing the validity of an explanation represents the same computational problem: if an explanation E has no counter, then there is no new theorem of E relative toT, belonging to the vocabulary p+ + Q. In symbols, given an algorithm to compute the set N ew(T, F) , we are interested in
and
Algorithms based on ordered-linear resolution [Chang and Lee, 1973] are known to perform this computation [Przymusinski , 1989; Oxusoff and Rauzy, 1989; Siegel, 1987; Inoue, 1991], and are used in many abductive pro cedures [de Kleer, 1986; Poole, 1989]. The explanation finding algorithm is not a concern of this paper. The results we present concern how to combine explanations in order to extract answers from a proof. We thus as sume such an algorithm exist and return the correct ex planations, and concentrate on the query answering pro cedure. The following one has been shown to correctly return yes/no answers, and is used in [Ginsberg, 1989; Przymusinski, 1989].
4 Note that N ew(T, -.F) does not include clauses implied by T alone because their negations are inconsistent with T and they cannot be counters. The predicates of P have their sign changed because we look for the negation of E.
Algorithm 2.6 (Yes/No Answering Procedure)
- Step 1. (Generate Elementary Explanations)
Compute elementary explanations of F relative to T.
- Step 2. (Combine Elementary Explanations)
Set the explanation E to the disjunction of all ele mentary explanations, and represent it in conjunc tive normal form (i.e., as a set of clauses).
Test if E has no counter, in which case answer
- Step 3. (Test Validity) "Yes"; otherwise answer "No".
This query answering procedure is not an exact imple mentation of Theorem 2.4 in one respect . The Theorem stipulates the need for an arbitrary valid explanation, while the answering procedure, in Step 2, only tests one for validity, namely the disjunction of all the elementary ones generated in Step 1. This is enough to return yes/no answers. The reason is that if a certain disjunction of valid explanations exist, then the maximal disjunction is valid. This maximal disjunction is then tested for valid ity. The example we present next illustrates the inability of this procedure to provide answer-extraction.
3 Example
I have to do some Prolog and Lisp programming this morning, and I need the manuals. Asking people around, I collect information about who has recently been using them. I know the office number of my colleagues, and I also know that normally people leave books in their offices. However, there are exceptions to this rule: for example, some of my colleagues work at home and don't bring back the books to the office. The information I have can be expressed with the following theory T, where predicate symbols and constants have obvious intended interpretations:
'Vx 'Vy'Vz had(x, y) t\ office(x, z) t\ -.ab(x) :::> at(y, z),
had(fred,prolog-manuaQ V had( mary,prolog-manual),
had( harold, prolog-manuaQ,
had( kurt, lisp-manuaQ,
office(fred, EJ225),
office( mary, EJ230),
office( harold, EJ235),
office( kurt, EJ240),
'Vx'Vy'Vz different(y,z) :::> -.at(x,y) v-.at(x,z),
different(EJ225, EJ230) t\ · · ·
· · · t\ different(EJ235, EJ240).
Where should I look for the manuals? Suppose I sub mit to the theorem prover the query
I am not really interested in knowing whether F is true or not. I would like to know how to get the manuals back,. and do so without inspecting all the offices around.
If we set P = { ab} and let the rest of the predicates vary, the minimal models of T can be divided in three groups, in each of which exactly one of -.ab(harold) ,
-.ab(mary) or -.ab(fred) is true. In the first group of these
holds. In the second and the third groups,
at(prolog-manual, EJ225) V at(prolog-manual, EJ230)
holds. Thus
at(prolog-manual, EJ225) V at(prolog-manual, EJ230) V at(prolog-manual, EJ235)
holds in all minimal models, and no subdisjunction does. Moreover, in all minimal models -.ab(kurt) is true, which means that
is another theorem of the circumscription. These two smallest disjunction of answers provide me with infor mation about where the manuals are.
However, Algorithm 2.6 produces the following.
Step 1. Three elementary explanations are computed:
- Step 2. The disjunction El V E2V E3 is transformed to conjunctive normal form. This is the conjunction of the following clauses:
- Step 3. These clauses, when added to T, produce no new theorem in the vocabulary of positive ab pred icates, showing that the disjunction of explanations is valid, as it has no counters. The procedure cor rectly answers "Yes".
There is no way instances of the query can be returned with this procedure. The reason is that the actual sub stitution for the variable in the query is lost in step 2, when the explanation is converted from disjunctive to conjunctive normal form. The rest of the paper de scribes a methodology and results on how to combine elementary explanation in a more careful way in order to produce the informative answers.
4 Answer Extraction
We consider informative answers to a query F relative to a circumscription CIRC (T; P; Z) to be the most specific instances of F entailed by the circumscription; in the sequel we simply call them answers to the query.
Definition 4.1 Let CIRC(T; P; Z) be a circumscriptive theory, F an existentially quantified query. An answer to F is a. formula A such that
1. CIRC(T; P; Z) f= A,
2. A f= F, and
- No A' different from A satisfies (1), (2) and A' f= A .
We now show how to produce such answers.
4.1 Obtaining Instances of the Query
As we said before, we assume that an explanation-finding algorithm returns explanations for the query. The prob lem we address is that of finding answers, that is, most specific disjunction of instances of the query entailed by the circumscription. To compute such instances of the query, we use Green's techniques for first-order logic [Green, 1969a; Green, 1969b], that consist of associating with F the clause
where x = x1, .. . , Xn stands for the variables ap pearing in F . During the proof of F, Ans keeps track of the substitutions for which F holds at no ex tra cost. The explanation-finding algorithm is thus the same resolution-based algorithm used by existing theorem provers for circumscription [Ginsberg, 1989; Przymusinski, 1989], but instead of supplying the nega tion of the query F to compute --.New(T, -.F), we sup ply F' and compute N ew(T, F'). 5 Accordingly, instead of obtaining explanations
for F, we obtain
where each Ansi keeps the substitutions for a disjunc tion Fi of instances ofF explained by Ei , that is,
4.2 Computing Answers
Given a query, the explanation-finding algorithm can compute the candidate answers F1, F2 , ... , the explana tions for each of these E 11 , E12, . . . , and their counters Cu1 , Cu2, .... An answer is a shortest disjunction of Fi that has a valid explanation, that is, for which at least one explanation exists with no counter.
Suppose two instances of the query F1 and F2 have elementary explanations E1 and E2 , neither of which is valid. E1 and E2 thus have counters C1 and C2. Now C = C1 1\ C2 is a candidate counter forE= E1 V E2 in the sense that as T + Ci f= --.E;, obviously T + C1/\ C2 f= -.E. But still C might not be a counter to E because, although each C; is consistent with T, C might not be. If Cis not consistent with T, and no other counter exist, E will be a valid explanation for F1 V F2 .
Thus while certain explanations may have counters, their disjunction might not, as the corresponding con junction of potential counters is inconsistent. Thus, com pared with theorem provers that return yes/no answers, the only additional computation needed is the consistency check on combinations of counters.
So the search problem consists of finding the disjunc tions of instances of the query such that the poten tial counters of their explanations are inconsistent. A counter C is inconsistent with T if and only if T F= --.C; and such counters belong to a particular vocabulary. It is thus rewarding to compute the following set of clauses.
5 The answer predicate Ans is added t.o the vocabulary p++Q.
Definition 4.2 Let CIRC(T; P ; Z) be a circumscriptive theory. A characteristic clause of CIRC(T; P; Z) IS a clause C that satisfies the following.
- Every literal of C belongs to p+ + Q.
2. T f= C.
- No other clause C' satisfies (1), (2) and C' F= C.
These are the restriction of the prime implicates [Reiter and de Kleer, 1987] ofT to a particular vocabulary. They can be computed with the same linear resolution algorithm used by the explanation-finding procedure, as shown by [Inoue, 1991].
We can take advantage of this set in at least the fol lowing ways.
- Let E be an elementary explanation, and C a counter to E . Then T + C F= --.E, and thus T F= --.C V -.E. As the explanation-finding algo rithm returns the shortest of such clauses, --.Cv --.E is a characteristic clause of the circumscription. In other words, to compute counters to an explanation, we consider the negation of its elementary compo nents. The counters are the negation of the comple ment within a characteristic clause.
- If T + C is inconsistent, and thus T F= --.C, then --.C is implied by a characteristic clause of the cir cumscription. This means that the consistency test on a combination of counters can be performed by entailment tests on the characteristic clauses.
The above ideas can be implemented using different search strategies, which are not our concern. The fol lowing is a possible implementation of an algorithm 6 to return informative answers to a query in a circumscrip tive theory.
Algorithm 4.3 (Query Answering Procedure)
Step 1. (Compilation)
Compute the characteristic clauses of the circum scription.
- Step 2. (Generate Elementary Explanations)
Compute elementary explanations of F relative to T.
Step 3. (Compute Counters)
A counter to an explanation is the complement of its elementary components within the characteristic clauses. If an explanation has no counters, output the instance of the query explained by it..
Step 4. (Combinations of Counters)
Compute the conjunctions of counters whose nega tion is entailed by a characteristic clause. Such a conjunction of counters is inconsistent with T , and the corresponding disjunction of elementary expl a nations is valid. If such an explanation has no other counters, the corresponding disjunction of instances of the query is an answer.
6 Strictly speaking, this is not an "algorithm". The rea son is , in Step 1 or 2, it may produce a.n infinite number of charact.erist.ic clauses or elementary explanations.
4.3 Example
We consider again the example of section 3.
- Step 1. Since ab is the only minimized predicate, the only characteristic clause of the circumscription is:
- Step 2. We provide the explanation-finding algorithm with the clause
and the answer predicate Ans.
Then we obtain the new clause
indicating that
explains
In a similar way,
explains
and
explains
- Step 3. C1 = ·ab(harold), is a counter to E1. C2 = ·ab(fred) A ·ab(mary) ; is a counter to E2 . Ea has no counters, thus Aa is output.
- Step 4. The only characteristic clause subsumes (in fact, is equivalent to) the disjunction of the nega tion of the two counters C1 and C2. This indicates that T + C1 A C2 is inconsistent, and as E1 V E2 has no other counter, it is a valid explanation for A1 V A2.
5 Conclusion
Nonmonotonic theorem provers often consist in a two step claBsica.l deduction - making a default proof in which explanations are collected and checking validity of the explanations. We showed that the substitutions needed for query answering are lost in this process, and a combination of theses need to be found to produce the required answers.
We presented a procedure for combining explanations in order to obtain informative answers, and results that enable an answering procedure to return the interesting answers with minimal search.
The importance of the results presented lies in their applicability t.o a wide cla.'Ss of systems that are either a restriction of circumscription, for example, databases using different types of closed-world assumptions (see [Przymusinski , 1989; Gelfond et al., 1989]), or similar de fault rea.'Soning systems having explanation-based proof theories [Poole, 1989; Geffner, 1990] .
Acknowledgment
We are grateful to Martin Abadi and Vladimir Lifschitz for their comments on earlier drafts.
@inproceedings{ijcai1991p64,
title = {Query Answering in Circumscription},
author = {Helft, Nicolas and Inoue, Katsumi and Poole, David},
booktitle = {Proceedings of the Twelfth International Joint Conference on
Artificial Intelligence, {IJCAI-91}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John Mylopoulos and Ray Reiter},
pages = {426--430},
year = {1991},
month = {8},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1991/64},
}
TY - CPAPER TI - Query Answering in Circumscription AU - Helft, Nicolas AU - Inoue, Katsumi AU - Poole, David T2 - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91 PB - International Joint Conferences on Artificial Intelligence PY - 1991 SP - 426 EP - 430 UR - https://ijcai.org/proceedings/1991/64 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: