Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering

Heng Zhang, Yan Zhang, Jia-Huai YouIJCAI 2016

Introduction

Ontology-Based Query Answering (OQA) serves as a cornerstone of Knowledge Representation and the Semantic Web. It involves querying a database of facts through the lens of a logical theory—an ontology—which provides additional context and inferential power. Over the past decades, a diverse "zoo" of ontology languages has emerged, including Description Logics like DL-Lite and $\mathcal{EL}$, as well as various extensions of Datalog. This proliferation raises a fundamental theoretical question: Does there exist a single, expressively complete language capable of capturing all others within the context of Conjunctive Query (CQ) answering?

This paper identifies Disjunctive Embedded Dependencies (DEDs) as the definitive answer to this question. The authors demonstrate that DEDs are expressively complete for Ontology-Based Conjunctive Query Answering (OCQA), meaning they can represent any ontology where query answering is semi-decidable, provided the ontology adheres to specific semantic properties.

The Semantic Framework of OCQA

To establish expressive completeness, the authors first formalize the boundaries of what constitutes an "OCQA ontology." They identify three essential semantic properties:

  1. Closure under query conjunctions: If the ontology supports two queries individually, it must support their conjunction.
  2. Closure under query implications: The ontology must respect the logical relationships between queries.
  3. Closure under injective database homomorphisms: The results of query answering should be preserved under mappings that preserve the distinctness of database elements.

An ontology satisfying these properties is termed a "quasi-OCQA ontology." The central challenge is determining whether a finite set of rules can capture any such ontology that is also recursively enumerable (RE)—that is, an ontology where the set of entailed answers can be listed by an algorithm.

Methodology: Simulating Computation with Logic

The proof of completeness relies on the ability of DEDs to simulate a Nondeterministic Turing Machine (NTM). This simulation is non-trivial due to the "negation gap": existential rules are inherently positive and cannot directly express the absence of information (e.g., "if X is not present, then Y").

To overcome this, the authors introduce the concept of "convergent" NTMs. This technique allows the simulation of negation-aware computation using only positive rules. Furthermore, they utilize a "universal model" approach. Instead of evaluating queries individually, they construct a single structural representation that encapsulates all possible answers for all possible queries for a given database. This effectively reduces a complex multi-query problem into a single structural representation.

Key Insights: The Necessity of Disjunction and Equality

A significant finding of this research is the "Power of Both." The authors prove that to achieve expressive completeness, a language requires both disjunction (the ability to represent alternative possibilities, e.g., $A \lor B$) and equality/existentials (the ability to posit the existence of anonymous objects).

The study highlights the limitations of simpler rule sets:

  • Disjunctive Tuple-Generating Dependencies (DTGDs): These lack the full power of existentials/equality and are shown to be insufficient.
  • Embedded Dependencies (EDs): These lack disjunction and are similarly incapable of capturing the full range of RE ontologies.

DEDs represent the "sweet spot" where these two features intersect, providing the necessary machinery to simulate any computable ontology. Notably, this result holds without the need for a "built-in linear order" on the database, a requirement often found in similar completeness results in finite model theory.

Results and Implications

The primary contribution of the paper is Theorem 7, which states that a quasi-OCQA ontology can be defined by a finite set of DEDs if and only if it is recursively enumerable. This establishes DEDs as the foundational "universal language" for the field.

Additionally, the authors provide a new characterization for classical database queries. Corollary 8 shows that such queries are definable by DEDs if they are RE and closed under injective homomorphisms. By providing a concrete example of a first-order rewritable ontology that cannot be expressed by DTGDs or EDs alone, the authors underscore the necessity of the full DED syntax.

Conclusion and Future Work

While DEDs are expressively complete, they are not a panacea. The paper focuses on expressiveness—what can be written—rather than tractability—what can be computed efficiently. In fact, query answering for the full class of DEDs is undecidable.

The value of this work lies in providing a theoretical ceiling. Future research can now use this semantic framework to identify expressively complete languages for more restricted, "well-behaved" classes of ontologies, such as those where query answering is in PTIME or can be rewritten into SQL. Furthermore, extending these results to more complex query languages involving negation or universal quantification remains a promising area of study.

Summary updated

BibTeX
@inproceedings{zhang2016expressive,
  author = {Heng Zhang and Yan Zhang and Jia-Huai You},
  title = {{Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure