Enhancing Existential Rules by Closed-World Variables

Giovanni Amendola, Nicola Leone, Marco Manna, Pierfrancesco VeltriIJCAI 2018 · DOI

TL;DR

This paper introduces "closed-world variables" to existential rules, a powerful formalism for knowledge representation. This enhancement allows for a more nuanced reasoning about "known" versus "arbitrary" individuals, extending existing decidable rule classes while preserving or only slightly increasing computational complexity.

What Problem Does This Paper Address?

Existential rules, a generalization of Datalog, are crucial for knowledge representation and ontology languages. Traditionally, these rules are interpreted under an "open-world assumption," meaning that anything not explicitly stated is unknown. This often requires introducing infinitely many "anonymous" individuals to represent unknown entities, making reasoning complex. Datalog, on the other hand, uses a "closed-world assumption," where unstated facts are considered false. This paper aims to bridge this gap by introducing a mechanism to distinguish between known (non-anonymous) and arbitrary individuals within existential rules, enabling more precise reasoning without sacrificing decidability.

Methods

The core innovation is the introduction of "closed-world variables" alongside standard variables. These closed variables are restricted to range over known individuals, while standard variables can range over all individuals. The authors then define "naive" and "refined" hybrid extensions of existing decidable existential rule classes (linear, weakly-acyclic, guarded, sticky, shy). They develop algorithms (Algorithm 1, 2, and 3) to reduce reasoning problems in these hybrid extensions to their standard counterparts, proving that decidability is preserved. They also analyze the computational complexity of query answering for these new classes, comparing them to the original ones.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Open and Closed Worlds: The introduction of closed-world variables offers a principled way to combine the expressiveness of open-world existential rules with the practical reasoning capabilities of closed-world assumptions.
  • Nuanced Reasoning: The ability to distinguish between known and arbitrary individuals allows for more precise modeling of real-world scenarios where some entities are explicitly known (e.g., specific products, individuals) while others are not.
  • Preserving Decidability: A significant achievement is demonstrating that these enhanced rule classes, even with the added expressiveness, largely maintain decidability for query answering, a critical property for practical applications.
  • Complexity Trade-offs: While decidability is preserved, the paper meticulously analyzes the impact on computational complexity. Some extensions maintain the original complexity, while others show a controlled increase, providing a clear understanding of the trade-offs involved.
  • Expressive Power: The authors show that their enhanced rule classes are strictly more expressive than their non-hybrid counterparts, meaning they can represent knowledge that was previously impossible to capture.

Key Results

  • The paper introduces hybrid extensions (CH and CH+) of five basic decidable datalog classes.
  • Decidability of query answering is proven for these hybrid extensions.
  • A detailed analysis of computational complexity (data and combined) is provided, summarized in Table 1. Most extensions maintain or slightly increase complexity compared to their base classes.
  • The paper demonstrates that the hybrid extensions are strictly more expressive than their non-hybrid counterparts, meaning they can capture more knowledge.
  • It's shown that linearH+ is strictly more expressive than the Description Logic ELH, even with bounded rules.

Limitations and Future Work

  • Further Ontology Language Exploration: The authors suggest investigating whether their naive or refined extensions can express other ontology languages and closing open questions regarding the expressivity of CH vs. CH+ for certain base classes.
  • Extending Complexity Analysis: They propose extending the computational complexity analysis to other known decidable rule classes.
  • Stratified Negation: The impact of stratified negation in rules and queries is suggested for reasoning about anonymity.
  • Nominal Schemas: The potential to mimic disjunction among nominals using existentially quantified closed variables is mentioned.
  • Implementation and Testing: A practical next step is implementing closed variables in existing datalog systems and testing their performance on real-world ontologies.

Summary updated

BibTeX
@inproceedings{amendola2018enhancing,
  author = {Giovanni Amendola and Nicola Leone and Marco Manna and Pierfrancesco Veltri},
  title = {{Enhancing Existential Rules by Closed-World Variables}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/232},
}
Figure