Defeasible disjunctive datalog

Matthew Morris, Tala Ross, Thomas MeyerFAIR 2019 · OpenReview

Introduction

Classical database logic, particularly Datalog, is a cornerstone of deductive database systems. However, its reliance on classical logic makes it notoriously rigid. In a standard Datalog environment, rules are absolute; if a system knows that "birds fly" and is then introduced to a "penguin" (a bird that does not fly), the resulting contradiction can break the underlying logic. To address this, researchers have sought to integrate "common sense" or defeasible reasoning—the ability to handle exceptions and typicality—into the Datalog framework.

This paper introduces a formal framework for Defeasible Disjunctive Datalog. By adapting the well-established KLM (Kraus, Lehmann, and Magidor) framework for non-monotonic reasoning, the authors provide a way for logic programs to reason about "typical" cases while gracefully handling exceptions without sacrificing formal rigor.

The Syntactic Challenge: Datalog+

One of the primary hurdles in applying defeasible reasoning to Datalog is the language's restrictive syntax. Standard Datalog is too "poor" to express the complex combinations of rules and negations required to define what constitutes a "rational" exception. To bridge this gap, the authors propose Datalog+, a temporary syntactic extension.

Datalog+ allows for the use of "compounds"—including negations, conjunctions, and disjunctions—that are not typically supported in standard Datalog engines. While not intended for final database implementation, Datalog+ serves as a vital mathematical bridge, allowing the authors to express and prove the KLM properties, which are the gold-standard requirements for any rational reasoning system.

Algorithmic Adaptation

The core contribution of the paper is the adaptation of three classic non-monotonic reasoning algorithms to the Datalog structure:

  1. Rational Closure (RC): This is the most conservative approach. If a conflict is detected at a specific level of "typicality," the algorithm discards the entire level to maintain consistency.
  2. Lexicographic Closure (LC): A more permissive alternative, LC attempts to retain as many rules as possible by analyzing subsets of rules rather than discarding entire levels.
  3. Relevant Closure (RelC): This approach targets only the rules directly relevant to a specific contradiction for removal.

To handle the lack of explicit negation in many Datalog variants, the authors utilize the $\perp$ (bottom/falsehood) literal. A rule is defined as "exceptional" if assuming its premise leads to a logical contradiction ($\perp$).

Key Insights and Results

The BaseRank Algorithm

The system's logic is powered by the BaseRank algorithm. This algorithm organizes rules into a hierarchy based on specificity. For example, general rules about birds are placed at the bottom of the hierarchy, while specific rules about exceptions (like penguins) are ranked higher. When a query is processed, the system identifies and ignores the less specific rules that would otherwise cause a contradiction.

Rationality vs. Relevance

A significant finding of the research is the distinction in formal "rationality" between these algorithms. The authors provide formal proofs that Rational Closure and Lexicographic Closure are "LM-rational," meaning they satisfy all necessary KLM properties in a Datalog context. Conversely, they discovered that Relevant Closure fails certain logical consistency checks, such as the "Or" and "CM" (Cautious Monotonicity) properties. This serves as a critical warning for developers: while Relevant Closure might seem intuitive, it may lead to logically inconsistent results.

Rule Normal Form (RNF)

To ensure compatibility with existing technology, the authors developed a method to convert complex Lexicographic statements back into standard Disjunctive Datalog rules using Rule Normal Form (RNF). This ensures that the theoretical advancements can eventually be implemented on top of existing Datalog engines.

Limitations and Future Directions

While this paper establishes a strong algorithmic foundation, the authors identify several areas for future research:

  • Semantics: The current work is primarily algorithmic. Future work is needed to develop a "semantic characterization" (such as ranked interpretations) to mathematically describe the "worlds" these rules create.
  • Computational Complexity: The Lexicographic Closure algorithm involves checking numerous subsets of rules, which may be computationally expensive in large-scale applications.
  • Datalog-Specific Properties: The authors suggest that instead of merely porting properties from propositional logic, future research should identify new rationality properties unique to the structure of Datalog itself.

Conclusion

By successfully adapting the KLM framework to Disjunctive Datalog, this paper provides a robust path forward for more flexible, "human-like" reasoning in deductive databases. The introduction of Datalog+ and the BaseRank algorithm allows for the formal handling of exceptions, ensuring that logic systems can remain consistent even when faced with the complexities of real-world data.

Summary updated

BibTeX
@inproceedings{morris2019defeasible,
  author = {Matthew Morris and Tala Ross and Thomas Meyer},
  title = {{Defeasible disjunctive datalog}},
  booktitle = {FAIR},
  year = {2019},
  url = {https://openreview.net/forum?id=7np4cfzbe6o},
}
Figure