Query Answering in Circumscriptive and Closed-World Theories

Teodor C. PrzymusinskiAAAI 1986

Introduction

In classical first-order logic, any fact that is neither explicitly stated nor logically provable remains in a state of "unknown" truth. However, human cognition and modern database systems frequently rely on the Closed-World Assumption (CWA): the pragmatic belief that if a piece of information is not known to be true, it can be safely assumed false. For instance, if a flight is not listed in a scheduling database, we assume it does not exist. John McCarthy’s circumscription provides a rigorous mathematical framework for this non-monotonic reasoning by minimizing the extension of certain predicates. Despite its theoretical power, circumscription often involves complex second-order logic, creating a significant gap between logical philosophy and practical implementation. This paper introduces MILO-resolution (Minimal model Linear Ordered resolution), a sound and complete algorithm designed to bridge this gap by providing a decidable method for query answering in circumscriptive theories.

The MILO-Resolution Algorithm

The primary contribution of this work is the development of MILO-resolution, a specialized variant of Ordered Linear (OL) resolution. While standard resolution techniques focus on finding any contradiction to prove a theorem, MILO-resolution incorporates specific constraints to ensure that the inference engine only considers minimal models—the "leanest" possible interpretations of a theory where as few facts as possible are held as true.

The algorithm introduces several key technical innovations:

  • Restricted Resolution: To maintain focus on minimization, resolution is strictly performed on the negative literals of the predicates being minimized ($P^-$).
  • Framed Literals: The process utilizes "framed" literals, typically denoted in brackets, to maintain a history of the resolution steps. This prevents the search from wandering into non-minimal logical territory.
  • Reduction Rules: These rules allow the algorithm to prune the search tree by deleting unframed literals that have already been "accounted for" by a corresponding framed literal.
Figure 1: An example of MILO-resolution showing a reduction step.

As illustrated in Figure 1, the algorithm processes a query such as ¬l(A,F). By applying a reduction rule, it simplifies the clause l(A,S) v ¬j(A) v [¬l(A,F)] into l(A,S) v ¬j(A). This pruning is essential for maintaining the efficiency and correctness of the search for minimal models.

Bridging Theory and Practice: Circumscription and ECWA

A pivotal insight of the paper is the formal proof that circumscription is essentially equivalent to the Extended Closed-World Assumption (ECWA). This is a significant "aha moment" in the field, as it links a high-level logical philosophy (circumscription) to a more concrete, database-oriented reasoning style (ECWA). By establishing this equivalence, the author demonstrates that MILO-resolution is not merely a tool for one specific logic but a unified framework capable of handling various types of non-monotonic reasoning, including the Generalized Closed-World Assumption (GCWA). This unification allows AI systems to make common-sense assumptions about what is false based on the absence of evidence for truth, all within a single inference engine.

Results and Decidability

The paper proves that for theories consisting of ground clauses (facts without variables), the MILO-resolution algorithm is decidable. This means the system will not enter an infinite loop; it is guaranteed to provide a definitive "yes" or "no" answer to a query. The author outlines a five-step "Decidable Query Answering Algorithm" that transforms a query into a normal form, explores the MILO-resolution tree, and employs a standard theorem prover to verify the final terminal clauses.

Figure 2: A MILO-resolution tree fragment for a query.

Figure 2 depicts a fragment of a resolution tree for the query ¬l(A,G). The branching paths represent the algorithm's exploration of potential minimal models. The terminal clauses reached at the end of these branches are then used to determine the truth value of the query under the circumscriptive theory. The author provides mathematical proofs for both the soundness (ensuring no incorrect answers) and completeness (ensuring an answer is found if it exists) of this procedure.

Conclusion and Future Work

While MILO-resolution represents a major step forward in making circumscription computationally accessible, the author notes that it inherits the inherent complexities and potential inefficiencies of general theorem provers. It is currently best viewed as an analytical tool rather than a high-speed production engine. To scale this approach for massive databases, the author suggests that future research should focus on strong syntactic restrictions—such as stratified databases—and the inclusion of "variable predicates" that can change to facilitate the minimization of others. Nevertheless, by providing a concrete algorithmic path for non-monotonic reasoning, this work lays the groundwork for more sophisticated and "common-sense" AI systems.

Summary updated

BibTeX
@inproceedings{przymusinski1986query,
  author = {Teodor C. Przymusinski},
  title = {{Query Answering in Circumscriptive and Closed-World Theories}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure