Verification of Knowledge Bases Based on Containment Checking

AAAI 1996

TL;DR

This paper tackles the crucial problem of verifying knowledge bases (KBs) by establishing a novel connection between KB verification and query containment in databases. This connection allows them to derive new, precise complexity results for verifying KBs with recursive Horn rules and to present the first complete algorithm for verifying hybrid KBs that combine Horn rules with description logic terminologies.

What Problem Does This Paper Address?

Building complex AI applications requires encoding vast amounts of domain knowledge into knowledge bases. A critical, yet challenging, step is verifying that this encoded knowledge is correct. A KB is considered verified if, for any valid input, it entails only correct outputs. Manually verifying KBs is tedious and error-prone. Previous work has focused on specific types of KBs (e.g., non-recursive Horn rules) and often lacked precise complexity analyses or complete verification algorithms, especially for more expressive KB formalisms. This paper addresses the need for robust verification methods for increasingly complex KBs, particularly those that integrate rule-based reasoning with structured knowledge representations like description logics.

Methods

The core of the paper's contribution lies in its novel approach to KB verification by framing it as a problem of query containment.

  • Horn Rule Verification: The authors show that verifying a Horn rule KB (with potentially recursive rules and interpreted predicates like '=', '<', '≠') is equivalent to checking if the "output constraint" predicate is contained within the "input constraint" predicate. This connection allows them to derive precise complexity bounds (NP-complete, doubly exponential, and undecidable) based on the recursiveness of the input/output constraint rules.
  • Hybrid KB Verification: For KBs combining Horn rules with description logic terminologies (specifically, ALCNR), they introduce a method to translate a class of constraints called separable tuple generating dependencies (tgds) into extended Horn rules and description logic constructs. This translation enables them to develop the first complete algorithm for verifying such hybrid KBs. The algorithm checks if the KB entails the output constraint predicate given the input constraint predicate and specific facts derived from the antecedent of each output constraint rule.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Query Containment Connection: The most significant insight is the formal equivalence between KB verification and query containment. This bridges two well-studied areas and allows for the transfer of results and techniques.
  • Complexity Characterization: By leveraging the query containment connection, the paper provides a precise characterization of the complexity of verifying Horn rule KBs, pinpointing exactly when the problem becomes undecidable (when output rules are recursive).
  • Handling Expressive Constraints: The paper introduces a method to handle more expressive input/output constraints using separable tuple generating dependencies (tgds), which go beyond simple Horn rules. This is crucial for real-world applications where constraints are often more nuanced.
  • Unified Verification for Hybrid KBs: The development of a complete algorithm for hybrid KBs (Horn rules + Description Logics) is a key step towards verifying more sophisticated AI systems that combine different reasoning paradigms.

Key Results

  • Complexity Bounds for Horn Rules:
    • Non-recursive input/output rules: NP-Complete.
  • One set recursive, the other not: Doubly exponential time complete.
  • Both sets recursive: Undecidable.
  • These results are extended to include interpreted predicates like '=', '<', '≠'.
  • Algorithm for Hybrid KBs: The paper presents the first complete algorithm for verifying hybrid KBs with ALCNR terminologies and Horn rules.
  • Separable TGD Translation: A method is provided to translate separable tgds into extended Horn rules and description logic constructs, enabling their use in verification.

Limitations and Future Work

  • Separable TGDs: While the paper handles separable tgds, it acknowledges that arbitrary tgds lead to undecidability. Future work could explore other classes of tgds or alternative methods for handling more complex constraints.
  • Counterexamples and Debugging: The current algorithms primarily answer "yes/no" for verification. The authors note that the algorithms can be modified to return counterexamples when a KB is not verified, and they are considering extending trace-based debugging methods for terminological KBs to hybrid KBs.
  • Production Rules: The current work focuses on first-order logic semantics for rules. Future work could extend these methods to handle production rules (e.g., OPS5-style) which may involve actions like deleting facts.

Summary updated

BibTeX
@inproceedings{1996verification,
  title = {{Verification of Knowledge Bases Based on Containment Checking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure