Indefinite and GCWA Inference in Indefinite Deductive Databases

Lawrence J. Henschen, Hyung-Sik ParkAAAI 1986

Introduction

In standard relational databases, the Closed World Assumption (CWA) serves as a fundamental principle: if a fact is not explicitly present in the database, it is assumed to be false. While this works effectively for Horn clauses (simple if-then rules), it fails in the context of Indefinite Deductive Databases (IDDBs). IDDBs allow for disjunctive information—statements like $P \lor Q$ (P or Q is true)—where the truth of individual atoms may be unknown.

Under these conditions, a standard query for $P$ should not return "False" if the database knows $P \lor Q$; instead, it should return "Indefinite." To handle this, researchers use the Generalized Closed World Assumption (GCWA). However, implementing GCWA has historically been computationally prohibitive, often requiring the generation of every possible model of the database at query time. This paper proposes a compilation-based approach to bridge the gap between high-level logic and efficient data retrieval.

The Problem: The Cost of "Maybe"

Previous methods for handling indefinite information were plagued by the "combinatorial explosion." To determine if a fact was true, false, or indefinite under GCWA, systems either had to perform complex logical proofs for every query or generate all minimal models of the database—an exponentially expensive task. The authors identify a need for a system that moves this logical heavy lifting from "query time" to "compile time," allowing the database to handle large-scale data without re-evaluating the underlying logic for every record.

Methodology: A Compilation-Based Approach

The core innovation of this research is the separation of the deductive process (the logic) from the data retrieval process (the physical records). This is achieved through several key techniques:

1. Potentially Indefinite Ground Clauses (PIGC)

The authors introduce the concept of PIGCs to identify a minimal set of positive clauses that characterize indefiniteness. By isolating these clauses, the system can determine if a query atom is potentially indefinite without scanning the entire database. This focuses the computational effort only on the "uncertain" parts of the data.

2. Representation Schemes

The paper evaluates three architectural schemes for organizing the database. The authors conclude that by storing negative information and non-Horn clauses in a specialized "Clausal Database" (CDB) while maintaining simple facts in a standard "Relational Database" (RDB), they can pre-calculate logical paths. This hybrid structure allows the system to treat the RDB as a source of ground truths that fill "templates" generated by the CDB.

3. Saturated Resolution

For non-recursive databases, the authors employ a resolution-based algorithm to pre-generate sets of clauses known as PTRUE, NH, and PSUB. These sets act as logical templates. At query time, the system simply checks the actual data against these templates to determine the truth value (True, False, or Indefinite), avoiding the need for real-time theorem proving.

4. Query Decomposition

Complex conjunctive (AND) and disjunctive (OR) queries are handled through a specialized truth table. The authors provide theorems to break these complex queries into simpler unit subqueries, maintaining a consistent algebraic treatment of the three-valued logic (True, False, Indefinite).

Key Insights and Results

The primary "aha moment" of the paper is that the logical structure of a database can be understood independently of the actual data. By compiling rules into generic queries first, the system achieves significant efficiency gains.

  • Efficiency: By moving deduction to a separate compilation phase, the system avoids the exponential costs associated with model generation during user interaction.
  • Representation Theorem: The authors mathematically prove that their proposed database architectures are equivalent to the full GCWA, providing a rigorous foundation for building practical IDDB systems.
  • Practical Application: Using a "Blood Type Relationship" database as a case study, the authors demonstrate how the system correctly distinguishes between blood types that are definitely false for a child versus those that are indefinite based on parental genetics.

Limitations and Future Work

While the paper provides a robust framework for non-recursive IDDBs, it acknowledges several hurdles for broader application:

  • Recursion: The compilation process for recursive databases is significantly more complex and remains an area for further research.
  • Saturation Complexity: The "simple saturation" method can grow rapidly as the number of indefinite rules increases. While the authors suggest "NH-reduction theorems" to mitigate this, the computational ceiling for extremely complex rule sets is still a concern.
  • Scalability: As a theoretical work, the paper lacks empirical benchmarks on modern big-data scales, which would be necessary to confirm its practicality in contemporary industrial environments.

Summary updated

BibTeX
@inproceedings{henschen1986indefinite,
  author = {Lawrence J. Henschen and Hyung-Sik Park},
  title = {{Indefinite and GCWA Inference in Indefinite Deductive Databases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure