Finite Model Reasoning in Hybrid Classes of Existential Rules

Georg Gottlob, Marco Manna, Andreas PierisIJCAI 2018 · DOI

TL;DR

This paper tackles the problem of finite model reasoning for existential rules, a crucial aspect of knowledge representation that has remained an open challenge. The authors demonstrate that finite query answering under the "tamed" combination of guarded and sticky existential rules has the same complexity as unrestricted query answering, effectively closing this problem.

What Problem Does This Paper Address?

Existential rules are powerful tools for knowledge representation and databases, allowing us to infer new information, including the existence of unknown entities. However, this expressiveness often leads to undecidability in query answering. To regain decidability, researchers have introduced restrictions like "guardedness" and "stickiness." Guarded rules are well-suited for forward reasoning, while sticky rules handle joins not expressible by guarded rules.

A significant advancement was the notion of "tameness," which allows combining guarded and sticky rules while preventing sticky rules from triggering guards of guarded rules. This "tamed" combination (denoted G|tS) has well-understood query answering complexity for unrestricted models. However, a key open problem was whether query answering remains decidable and what its complexity is when restricted to finite models, which is often a more realistic assumption in practical applications. This paper aims to solve this open problem.

Methods

The core of the paper's contribution lies in proving that the class of tamed guarded and sticky rules (G|tS) is "finitely controllable." This means that for any query and database, the answers obtained from finite models are the same as those obtained from unrestricted models. This property is crucial because it allows us to leverage the known complexity of unrestricted query answering for G|tS to determine the complexity of finite query answering.

The proof strategy involves:

  1. Stratified Case Analysis: First, the authors analyze a simpler, "stratified" subclass of tamed rules (G5S). They prove that this subclass is finitely controllable, providing a foundational result and a useful tool for the main problem.
  2. Conversion to Stratified Rules: The main technical result is showing that any tamed set of guarded and sticky rules (Σ ∈ G|tS) can be converted into an equivalent stratified set of rules (Σ ∈ G5S) and a modified query (q). This conversion preserves finite answers.
  3. Model-Theoretic Construction: A key technique is the construction of "sticky-supported" models, which form a universal finite model set. This allows them to bridge the gap between finite and unrestricted models for the stratified case.
  4. Embedding and Rewriting: For the general tamed case, they develop a sophisticated embedding technique to convert sticky rules into guarded ones, allowing the entire set of rules to be transformed into a stratified form. This involves a detailed analysis of how variables propagate and are handled.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Finite Controllability is Key: The paper hinges on the concept of "finite controllability," which establishes an equivalence between finite and unrestricted query answering. Proving this property for G|tS is the central achievement.
  • Tameness Doesn't Always Preserve Finite Controllability: A surprising finding is that simply combining two finitely controllable classes of rules using tameness does not guarantee finite controllability for the combined class. This is demonstrated with a counterexample involving full TGDs. This highlights the need for a deeper, tailored analysis for G|tS.
  • Stratification as a Bridge: The paper leverages a simpler, stratified subclass of rules (G5S) as an intermediate step. Proving finite controllability for this subclass and then showing how to convert general tamed rules into this stratified form is a clever strategy.
  • Sticky-Supported Models: The introduction of "sticky-supported" models is a novel technical contribution, providing a universal finite model set that is crucial for the proof.
  • Expressive Power Distinction: The paper also explores the expressive power of stratified vs. tamed rules, showing that tamed rules are strictly more expressive in terms of program expressive power, meaning there are tame rule sets that cannot be simulated by stratified ones with the same query answering capabilities.

Key Results

  • Finite Controllability of G5S: The paper proves that the stratified subclass of tamed guarded and sticky rules (G5S) is finitely controllable.
  • Finite Controllability of G|tS: The main result is that the entire class of tamed guarded and sticky rules (G|tS) is finitely controllable.
  • Complexity of Finite Query Answering for G|tS: As a direct corollary of finite controllability, the paper establishes that finite query answering for G|tS has the same complexity as unrestricted query answering: 2EXPTIME-complete in combined complexity and PTIME-complete in data complexity.

Limitations and Future Work

  • Complexity of Refutation: The authors identify a direction for future work in developing algorithms to efficiently refute candidate answers (i.e., prove that a tuple is not a certain answer). This would complement existing algorithms for proving entailment.
  • Practical Algorithms: While theoretical complexity is established, the paper suggests that the ideas developed, particularly around finite models and efficient checking, could lead to practical algorithms for real-world knowledge representation systems.
  • Generalization: The paper hints that the techniques used for G5S might be generalizable to other classes of finitely controllable and UCQ-rewritable rules.

Summary updated

BibTeX
@inproceedings{gottlob2018finite,
  author = {Georg Gottlob and Marco Manna and Andreas Pieris},
  title = {{Finite Model Reasoning in Hybrid Classes of Existential Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/253},
}

Loading related content...

Figure