In knowledge representation and database theory, we often need to reason with rules that can infer the existence of unknown entities. These are known as existential rules (or tuple-generating dependencies). A classic example is the rule governing family trees: Every person has a parent who is also a person.
Mathematically, this looks like: $$\forall x (\text{Person}(x) \rightarrow \exists y (\text{Parent}(x, y) \wedge \text{Person}(y)))$$
If we know that "Alice" is a person, this rule implies there must be some individual—let's call them $y_1$—who is Alice's parent. Because $y_1$ is also a person, the rule fires again, implying the existence of $y_1$'s parent, $y_2$. This triggers an endless cascade of value invention.
The standard algorithm used to compute these logical implications is called the chase. The chase works by forward-chaining: it repeatedly applies rules to a database to materialize new facts. However, as this simple example illustrates, the introduction of existential quantifiers creates a fundamental vulnerability: the chase can easily enter an infinite loop, generating an unbounded sequence of anonymous objects. As noted by Michaël Thomazo in From EL to Tractable Existential Rules with Complex Role Inclusions, this non-termination risk makes query answering over existential rules inherently undecidable in the general case.
The Undecidability Barrier and Syntactic Safety
To build practical reasoning engines, we must find ways to guarantee that the chase will stop. A natural first question is: Can we write a meta-algorithm to check whether a given set of rules will terminate?
Unfortunately, Bernardo Cuenca Grau et al. demonstrated in Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies that determining whether the chase will terminate on a specific set of rules and facts is an undecidable problem. Because a universal termination checker is impossible, research has shifted toward identifying sufficient syntactic conditions—structural guardrails that guarantee termination.
These guardrails typically rely on advanced notions of acyclicity. By analyzing how variables depend on one another across rule heads and bodies, we can detect whether a cycle can cause infinite value invention. For instance, when rules include equality constraints (asserting that two invented entities are actually the same), the chase becomes even more unpredictable. To handle this, David Carral et al. introduced Equality Model-Faithful Acyclicity (EMFA) in Checking Chase Termination over Ontologies of Existential Rules with Equality, providing a highly efficient way to verify termination without incurring massive performance penalties.
When rules allow for disjunctions (logical "OR" conditions), the chase branches, creating multiple potential models. To tame this complexity, Lukas Gerlach 0002 et al. developed profiles like DMFA and DMFC in General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase, which successfully predict the termination behavior of nearly all real-world rule sets.
Bypassing the Chase via Rewriting and Goal-Driven Analysis
What if we want to reason with rules that might cause an infinite chase, but we want to avoid running an infinite algorithm altogether? Two prominent strategies have emerged to bypass forward-chaining materialization: Datalog rewriting and goal-driven query answering.
Datalog Rewriting
Standard Datalog is a rule language that forbids existential quantifiers in rule heads. Because it cannot invent new constants, its execution domain is strictly bounded by the constants already present in the database, meaning it is guaranteed to terminate.
If we can transform a complex set of existential rules into an equivalent Datalog program, we can completely avoid the infinite chase. Michael Benedikt et al. achieved this for guarded existential rules (where all variables in a rule's body appear together in a single "guard" atom) in Datalog Rewriting for Guarded TGDs. Furthermore, the authors in Rewriting the Infinite Chase introduced "shortcut" rules that compile potentially infinite forward-chaining derivations into a finite, one-pass Datalog execution model, allowing standard relational database engines to safely evaluate the queries.
Goal-Driven Query Answering
Forward-chaining materializes every possible fact, which is why it falls into infinite loops. Goal-driven (or backward-chaining) approaches work in reverse: they start from the user's query and only evaluate the rules necessary to answer it.
Michael Benedikt et al. pioneered this for existential rules with equality in Goal-Driven Query Answering for Existential Rules With Equality. By combining a specialized relevance analysis with a magic sets algorithm, their framework prunes away the rules and data that would otherwise trigger infinite entity generation, isolating only the finite reasoning paths required to return a correct answer.
The Expressive Power of Terminating Rules
A lingering concern with forcing the chase to terminate—either through strict syntactic constraints or rewriting—is that we might strip the language of its logical power. If we outlaw the rules that cause infinite loops, do we lose the ability to express complex real-world relationships?
A foundational result by Camille Bourgaux et al. in Capturing Homomorphism-Closed Decidable Queries with Existential Rules resolved this concern. The authors proved a powerful completeness theorem: any database query that is both decidable and closed under homomorphisms can be perfectly expressed by a set of existential rules for which the standard chase is guaranteed to terminate.
This means that terminating existential rules are not a compromised, weak fragment of logic. They are theoretically complete for a massive class of practical database problems. The primary advantage of these finite-chase fragments lies in their succinctness. As Heng Zhang et al. showed in Existential Rule Languages with Finite Chase: Complexity and Expressiveness, while terminating rule sets share the same data complexity as more permissive languages, they allow developers to express highly intricate domain logic using significantly smaller, more maintainable rule sets without ever risking system non-termination.
Key Foundational Work
A Sequential View of AND-Parallelism Through Partial AND-Processes (1989) — contributed 1 concept elements to this direction.
Simulating Non-Deductive Reasoning (1983) — contributed 1 concept elements to this direction.