Taming the Infinite Chase in Existential Rules

This direction is split into other directions: infinite chase problem, undecidability of flat rewriting. Its last version stays readable and citable here.

Version 1 of 176 papers107 conceptsfrozen 2026-10-04

In the world of automated reasoning, a simple rule like "every person has a parent" is surprisingly dangerous. If a database knows about one person, Alice, this rule implies the existence of a parent, Bob. But Bob is also a person, implying a parent, Carol, and so on. This recursive "invention" of new, anonymous individuals can trigger an infinite chain of inferences.

This phenomenon is the central challenge of Ontology-Based Query Answering (OBQA). To answer queries over data governed by such rules, researchers use a procedure called the chase. The goal of recent research is to find ways to make this chase stop, or to bypass it entirely, without losing the ability to reason about "hidden" entities.

The Chase and the Problem of Infinity

The chase is a materialization algorithm: it takes a set of facts and iteratively applies rules until no more new information can be derived. As Michaël Thomazo explains in Interrogation de données au travers d'une ontologie, the chase acts as a bridge between the data we have and the logical implications of the ontology.

However, because existential rules (also known as tuple-generating dependencies) allow for the creation of new identifiers, the chase often fails to terminate. This "infinite chase" makes query answering undecidable in the general case. As Jean-François Baget and colleagues noted in Extending Decidable Cases for Rules with Existential Variables, even simple dependencies can lead to an infinite search space where a proof might exist but never be found.

Identifying Decidable Fragments

To make reasoning practical, researchers identify "fragments" of logic—specific syntactic restrictions that guarantee the chase will either stop or behave predictably.

One major strategy is guardedness. In a guarded rule, all variables in the rule's body must appear together in a single "guard" atom. This restriction, explored by Georg Gottlob and Andreas Pieris in Beyond SPARQL under OWL 2 QL Entailment Regime, ensures that the "tree-width" of the generated data remains bounded, preventing the logic from spiraling into unmanageable complexity.

Another approach is acyclicity. If we can prove that the dependencies between rules don't form certain types of cycles, we can guarantee the chase will terminate. David Carral and Lukas Gerlach 0002 have pushed this frontier with notions like DMFA (Disjunctive Model-Faithful Acyclicity), which can successfully predict termination for nearly 99% of real-world rule sets (General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase).

Rewriting the Infinite into the Finite

If the chase is infinite, why run it at all? A powerful alternative is Datalog Rewriting. The idea is to transform the complex existential rules into a simpler Datalog program that a standard database engine can execute.

In Rewriting the Infinite Chase, Maxime Buron, Boris Motik, and Michael Benedikt describe a "one-pass" approach. Instead of generating an infinite sequence of new objects, they create "shortcut" rules that simulate the effect of those objects within the existing data. Similarly, the Drewer system, developed by Peng Xiao and Kewen Wang, uses rule-splitting and shared data structures to produce compact Datalog rewritings that avoid the exponential "query blow-up" common in earlier methods (Practical Datalog Rewriting for Existential Rules).

Handling Equality and Messy Data

The problem becomes even harder when rules include equality (e.g., "if two people share a social security number, they are the same person"). Equality can cause the chase to "shrink" the data by merging nodes, which interacts poorly with the "expansion" caused by existential rules.

David Carral addressed this in Checking Chase Termination over Ontologies of Existential Rules with Equality by introducing EMFA (Equality Model-Faithful Acyclicity). This allows systems to check for termination even when rules are constantly merging and creating entities. This is crucial for real-world applications like Entity Resolution, where Lucian Popa and Phokion G. Kolaitis have integrated these logical frameworks to ensure consistent query answers even when data is redundant or conflicting (Combining Entity Resolution and Query Answering in Ontologies).

Why This Works

The intuition behind this entire research direction is that structure implies decidability. By restricting how rules can interact (through guardedness) or how they can trigger each other (through acyclicity), we ensure that the "information flow" in a knowledge base is either finite or sufficiently repetitive that we can summarize it. Whether through the optimized chase variants of Marie-Laure Mugnier or the goal-driven pruning of Michael Benedikt, the goal is to turn the "infinite" potential of logic into the "finite" reality of database computation.

Papers in this version

Showing 60 of 76 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_taming_the_infinite_chase_in_existential_647f897f,
  title = {Taming the Infinite Chase in Existential Rules},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/taming-the-infinite-chase-in-existential-rules/rdr_647f897fa0b94a39aac87ccae6c112f4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_taming_the_infinite_chase_in_existential_647f897f_v1,
  title = {Taming the Infinite Chase in Existential Rules},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/taming-the-infinite-chase-in-existential-rules/rdr_647f897fa0b94a39aac87ccae6c112f4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}