Introduction
Existential rules, often referred to as Datalog+/-, provide a robust framework for knowledge representation by allowing the implication of unknown entities. While reasoning with positive queries is well-understood through the use of universal models, the introduction of negation-as-failure presents significant challenges. This paper bridges the gap between theoretical semantics and practical reasoning by identifying syntactic conditions that allow standard, efficient algorithms to remain consistent with the "core" model—the most cautious theoretical reference point.
The Challenge of Negation in Existential Rules
In standard Datalog, a single "least model" typically suffices for query answering. However, existential rules can generate multiple universal models that disagree on what is not true. This ambiguity makes it difficult to define a "correct" answer for negative queries. While the core (the smallest universal model) is the ideal reference for "cautious" semantics, computing it is DP-complete and impractical for large datasets.
Methodology: A Hierarchy of Safety Conditions
To address the computational cost of the core, the authors propose a hierarchy of syntactic conditions. These conditions ensure that queries can be answered using more efficient structures, such as the results of a "chase" algorithm, without losing the semantic guarantees of the core.
- Affection-Safe Queries: A strict condition where negated atoms only refer to constants unaffected by the "null" values generated by existential rules.
- Core-Safe Queries: A more flexible condition using restraints to identify variables that are safe from being pruned in a core model.
- Effectively Core-Safe: A safety condition that accounts for the specific execution order of the chase algorithm.
- Core-Safe Stratification: An extension for "normal rules" (rules with negation in their bodies), allowing for layered evaluation that preserves "perfect core" semantics.
Key Insights and Theoretical Map
The central contribution is a mapping of the trade-offs between query generality and model specificity. As query syntax is restricted, broader and easier-to-compute classes of models become viable.
The "aha moment" of this research is that the expensive core model does not actually need to be computed. If rules and queries satisfy these syntactic checks, the standard restricted chase algorithm is guaranteed to produce results equivalent to the core.
Key Results
- Theorem 1: Confirms that if a query is satisfied in the core, it is satisfied in all universal models, establishing the core as the proper foundation for cautious semantics.
- Theorems 2 & 3: Prove that for Affection-Safe and Core-Safe queries, any standard chase result provides the same answer as the core.
- Theorem 5: Demonstrates that core-safe stratified rules result in a unique model (up to isomorphism), providing stable semantics regardless of the specific stratification used.
Limitations and Future Outlook
While this work provides a solid theoretical foundation, several challenges remain. The current approach assumes the existence of a finite core model, which is not guaranteed when existential rules lead to infinite structures. Additionally, while checking safety conditions is cheaper than computing a core, it remains $\Sigma^P_2$-complete in the worst case. Future efforts will focus on integrating these safety checks into production rule engines like VLog or RDFox to bridge the implementation gap.
Summary updated