Introduction
In the fields of database theory and knowledge representation, existential rules—also known as tuple-generating dependencies (TGDs)—serve as a cornerstone for representing background knowledge and performing automated reasoning. However, a persistent challenge in using these rules is the "chase" algorithm, a fundamental procedure for query answering. In many cases, the chase may fail to terminate, leading to undecidability. This research addresses a long-standing theoretical question: exactly how much expressive power do existential rules possess when we restrict ourselves to fragments where the chase is guaranteed to terminate?
This paper provides a definitive answer, proving that existential rules under the standard chase are powerful enough to capture the entire class of decidable queries that are preserved under homomorphisms. This result effectively establishes the theoretical upper bound for the expressivity of terminating existential rules.
The Problem: Expressivity vs. Decidability
Existential rules allow us to infer the existence of new entities (e.g., "If $X$ is a Professor, then there exists a $Y$ such that $Y$ is a Faculty Member and $X$ works in $Y$"). While powerful, this ability to create new individuals can lead to infinite loops during the reasoning process. To ensure practical utility, researchers often focus on "terminating" fragments of existential rules.
The central question explored here is whether there is a gap between what these terminating rules can express and the broader class of "homomorphism-closed" queries. A query is homomorphism-closed if, whenever it is true for a database $D$, it remains true for any database $D'$ that $D$ can be mapped into via a homomorphism. Since existential rules naturally produce homomorphism-closed queries, the authors sought to determine if terminating rules could represent all such queries that are otherwise decidable.
Methodology and Theoretical Construction
The authors utilize a sophisticated three-step logical construction to prove that any decidable, homomorphism-closed query $Q$ can be represented by a set of existential rules $\Sigma$ for which the standard chase terminates:
- Turing Machine Simulation: The construction begins by writing rules that simulate a Turing Machine (TM) capable of deciding the query $Q$. This involves using disjunctive rules to "guess" the structure of the database and its potential completion.
- The "Emergency Brake" Mechanism: To guarantee termination, the authors implement a safety mechanism. If the chase detects that the "guessed" database structure is invalid (for instance, if it contains cycles where a linear order is expected), the process triggers an "emergency brake," halting the creation of new entities.
- Eliminating Disjunction: Finally, the authors employ a transformation to convert the intermediate disjunctive rules into standard existential rules. This step ensures the final rule set remains within the intended logic fragment while preserving the query's semantics.
Key Insights
The Power of the Standard Chase
A significant finding of this work is the equivalence of different chase variants. The authors demonstrate that the "standard chase" is just as expressive as the more computationally complex "core chase." Furthermore, they show that adding disjunction to the heads of rules does not increase the class of decidable queries that can be expressed, as standard existential rules already reach the theoretical limit.
The Recognizability Trade-off
While the paper establishes the immense power of terminating existential rules, it also identifies a fundamental limitation: non-recognizability. Using a diagonalization argument, the authors prove that there is no algorithm that can automatically determine whether an arbitrary set of existential rules will terminate under the chase. This creates a "no free lunch" scenario where the language is maximally expressive, but its boundaries are computationally invisible.
Conclusion and Future Directions
This research closes a significant chapter in the study of existential rules by proving they are complete for decidable, homomorphism-closed queries. It confirms that the standard chase is a robust and sufficient mechanism for capturing this broad class of logic.
However, the authors note that while these queries are expressible, they are not necessarily efficiently computable in this form. Future research is directed toward complexity analysis—specifically, finding "worst-case optimal" constructions. While we now know what can be expressed, the next challenge lies in determining how to express these queries in a way that leads to optimal performance in practical reasoning systems.
Summary updated