Characterizing the Program Expressive Power of Existential Rule Languages

Heng Zhang, Guifei JiangAAAI 2022 · DOI

Introduction

In the field of Knowledge Representation and Reasoning, Ontology-Mediated Query Answering (OMQA) has emerged as a vital paradigm. By augmenting traditional databases with an ontology—a set of logical rules—researchers can uncover implicit facts and reason over complex domain knowledge. While the "data expressive power" of these rule languages (what queries they can define over a database) is well-documented, their "program expressive power" (what domain knowledge can be encoded within the rules themselves) has remained largely unmapped.

This research provides the first comprehensive theoretical characterization of the program expressive power for existential rule languages, such as Datalog±. By establishing formal boundaries using model theory and automata, the authors clarify the capabilities of various rule flavors, including linear, disjunctive, and standard tuple-generating dependencies (TGDs).

Data vs. Program Expressive Power

To understand the contribution of this work, one must distinguish between two types of expressivity:

  1. Data Expressive Power: Measures the class of queries a language can define. This is the standard metric used to compare languages like Datalog or SQL.
  2. Program Expressive Power: Measures the class of ontologies (sets of rules) that can be expressed. For engineers building knowledge graphs, this determines whether a chosen language can actually represent the specific logic and constraints of their application domain.

Prior to this study, the boundaries for many popular existential rule languages were not formally defined, leaving a gap in our understanding of how different syntactic restrictions impact the ability to model real-world knowledge.

Methodological Framework

The authors employ a rigorous mathematical approach combining logic, model theory, and formal language theory to draw these boundaries:

  • Nondeterministic Chase: The "chase" is a fundamental algorithmic tool for reasoning with rules. The authors introduce a nondeterministic variant capable of handling disjunctions (OR-logic) to establish soundness and completeness across different rule sets.
  • Encoding and Translation: A key technique developed in the paper involves encoding nondeterministic facts and disjunctive logic into standard, deterministic TGDs. This allows for a formal comparison between languages, identifying when a complex language can be simplified without a loss of semantic meaning.
  • Tree Automata: For linear TGDs—rules characterized by having only a single atom in the body—the authors utilize Nondeterministic Tree Automata (NTA). They demonstrate that the queries produced by these rules are "recognizable" by specific classes of tree automata, effectively bridging the gap between logic and automata theory.

Key Insights: Disjunction and Linearity

The Redundancy of Equality

The research suggests that explicit equality symbols in rules are often unnecessary. If an ontology is closed under database homomorphisms and constant substitutions, equalities can be replaced with fresh relation symbols without sacrificing expressive power.

Disjunction in Query Answering

A significant finding concerns the role of disjunction (DTGDs). The authors show that for standard Conjunctive Queries (CQs), adding disjunction does not increase program expressive power. Any set of disjunctive rules can be translated into standard TGDs for the purpose of CQ answering. However, for Union of Conjunctive Queries (UCQs), disjunction becomes meaningful. The authors identify "query constructivity" as the specific property that determines when disjunction provides a genuine boost in power.

The Tree-Like Nature of Linear Rules

The study confirms that linear TGDs are fundamentally "tree-like." Their expressive power is precisely captured by the intersection of data constructivity and the ability of a tree automaton to recognize the resulting queries.

Formal Characterizations

The paper establishes several landmark theorems that provide "if and only if" semantic characterizations:

  • Theorem 5: Defines disjunctive rules (DTGDs) as the class of ontologies closed under homomorphisms and constant substitutions.
  • Theorem 7: Establishes that for CQ-answering, DTGDs and standard TGDs share identical program expressive power.
  • Theorem 12: Proves that a disjunctive ontology is equivalent to standard TGDs if and only if it admits query constructivity.
  • Theorem 16: Provides the first semantic characterization of linear TGDs using data constructivity and NTA-recognizability.

Limitations and Future Directions

While this work provides a definitive theoretical map, several areas remain for future exploration. The translations provided (such as converting disjunctions into TGDs) are theoretical proofs of existence and may involve an exponential increase in the number of rules, potentially limiting immediate practical application in large-scale systems.

Furthermore, the scope is primarily limited to TGDs and their variants, leaving deeper investigations into Negative Constraints or Equality-Generating Dependencies (EGDs) for future work. Finally, while the link to tree automata suggests potential for optimized query engines, the development of such systems remains an open engineering challenge.

Summary updated

BibTeX
@inproceedings{zhang2022characterizing,
  author = {Heng Zhang and Guifei Jiang},
  title = {{Characterizing the Program Expressive Power of Existential Rule Languages}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20540},
}
Figure