Existential Rules and the Chase

📍 Where we are: Part IV · Datalog and the Chase — Chapter 13. Datalog climbed the immediate-consequence operator to its least fixpoint, deriving every fact that follows from the constants already on the table; now we let a rule's head assert that something must exist even when no constant names it, and watch a new engine — the chase — invent that something.

Datalog is powerful, but it has one blind spot that matters enormously for ontologies: every atom it derives is built from constants that were already present. It can shuffle alice, bob, and carol into new relationships, but it can never conclude that there is someone who plays a role no named individual fills. Description logic does this constantly — "every professor advises some student" is an existential claim — so to model ontologies as rules we need rules whose heads can reach past the known constants. This chapter builds that rule form, the existential rule, and the forward-reasoning procedure that satisfies it, the chase.

The simple version

Imagine a guest list that says "every professor must be seated next to a student." You scan the table: alice is a professor, but the seat beside her is empty. The rule does not tell you which student — only that one is required. So you write a placeholder card, "Student #1," and set it down. That card is a fresh null: a stand-in for someone who must exist but has no name yet. The chase is nothing more than walking the table, and every time a rule demands a companion who is not already there, laying down one more placeholder — until either every rule is satisfied, or you discover the rule keeps demanding placeholders for the placeholders, forever.

What this chapter covers

• Why Datalog is not enough — a Datalog head only recombines existing constants; "every professor advises some student" needs a witness that may not be named anywhere in the data.
• A TGD, decoded — the existential rule as a tuple-generating dependency: body → head, where the head may carry variables the body never bound.
• The chase step — match the body, and for each head-only variable mint a fresh null (_n1, _n2, …); the loop that adds the new atoms and counts the firings.
• Oblivious versus restricted — the oblivious chase fires on every match; the restricted chase first checks whether a witness already exists and skips if so — three nulls instead of five on the academic instance.
• The committed run, as a table — restricted and oblivious side by side, with the real firing and null counts the companion prints.
• When the chase diverges — an existential cycle (every researcher was advised by some researcher) that mints witnesses without end, run under a step cap so the divergence is visible but bounded.
• The bridge to certain answers — an infinite or huge chase cannot be materialized, yet we still want query answers; the next chapter reads them off the chase without building it whole.

Why Datalog cannot invent a witness

A Datalog rule is a Horn clause: a conjunctive body implies a single atom, and every variable in the head also appears in the body. That last requirement — head variables are body variables — is exactly what keeps Datalog safe and its fixpoint finite. Because every head variable is bound to a constant by the body match, the head can only restate a relationship among constants the data already mentions: run the immediate-consequence operator forever and you never coin a new individual, only new tuples over the old ones.

That is precisely the wrong tool for an ontology axiom like Professor ⊑ ∃advises.Student — "every professor advises some student." Read as a rule, its head must claim the existence of an advisee even when the professor advises no one on record. In first-order logic the axiom is

$$\text{Professor}(x) \;\rightarrow\; \exists y.\; \text{advises}(x, y) \wedge \text{Student}(y).$$

The decoder, symbol by symbol: $\rightarrow$ reads "implies"; $\exists y$ reads "there exists some $y$"; the dot after $\exists y$ separates the quantifier from the claim it governs; and $\wedge$ reads "and." The variable $y$ appears only in the head — nothing in the body Professor(x) binds it. A Datalog engine cannot fire this rule, because it has no constant to substitute for $y$. To make it fire, we must be willing to invent one.

A TGD, decoded

A rule of this shape is a tuple-generating dependency (TGD), also called an existential rule [1]. Its general form is a conjunction of body atoms implying a conjunction of head atoms, where the head may introduce existentially quantified variables that the body does not:

$$\underbrace{\phi(\vec{x}, \vec{z})}_{\text{body}} \;\rightarrow\; \exists \vec{y}.\; \underbrace{\psi(\vec{x}, \vec{y})}_{\text{head}}.$$

Here $\vec{x}$ are the frontier variables shared by body and head (they carry known values across), $\vec{z}$ are body-only variables, and $\vec{y}$ are the head-only existential variables — the witnesses to be invented. In the companion file the terminating example encodes two such rules (chase.py lines 195-200):

TERMINATING_TGDS = [
    ([("Professor", "?x")],
     [("advises", "?x", "?y"), ("Student", "?y")]),
    ([("Student", "?x")],
     [("affiliated", "?x", "?z"), ("Institution", "?z")]),
]

Each TGD is a (body, head) pair of atom lists, following the same term convention as the Datalog chapter (chase.py lines 32-33): variables begin with ?, nulls begin with _n, and everything else is a constant. In the first rule ?x is a frontier variable (it appears in both body and head) while ?y is existential — it appears only in the head. Finding those head-only variables is the job of one small helper (chase.py lines 84-92):

def _existential_vars(body, head) -> list:
    body_vars = {a for atom in body for a in atom[1:] if is_var(a)}
    head_vars = [a for atom in head for a in atom[1:] if is_var(a)]
    seen, out = set(), []
    for v in head_vars:
        if v not in body_vars and v not in seen:
            seen.add(v)
            out.append(v)
    return out

It collects the set of variables the body binds, walks the head's variables in order, and keeps exactly those the body never bound. For rule one it returns ["?y"]; for rule two, ["?z"]. Those are the variables the chase will have to fill with fresh nulls.

The chase step: mint a fresh null

The chase is forward chaining for TGDs. It repeatedly finds a body match — a homomorphism from the body atoms into the current instance — and fires the rule. Firing means applying the frontier bindings to the head, and, for each existential variable, minting a brand-new null that appears nowhere else. The core of the loop (chase.py lines 106-156) is the minting-and-adding block:

                sub = dict(h)
                for v in exvars:
                    null_ctr += 1
                    sub[v] = f"_n{null_ctr}"
                new_atoms = [_apply(atom, sub) for atom in head]
                added = [a for a in new_atoms if a not in inst]
                if added:
                    inst.update(added)
                    steps += 1
                    changed = True

Read it as the chase step made literal. h is the body match (frontier variables bound to existing terms). The loop for v in exvars walks the head-only variables from _existential_vars, and for each one bumps a global counter and assigns a fresh null — so the first invented witness is _n1, the next _n2, and no two firings ever collide. _apply substitutes both the frontier bindings and the new nulls into every head atom, added keeps only atoms genuinely new to the instance, and if anything was added the instance grows, a firing is counted, and changed = True keeps the outer loop alive. When a full pass adds nothing, changed stays False and the chase terminates (chase.py line 152) — the same "a round changed nothing" exit test the fixpoint loop used, now over an instance that can contain invented individuals.

The chase satisfies existential rules by inventing anonymous nulls; the restricted chase skips bob because he already advises a student, while the oblivious chase mints a redundant witness, and an existential cycle spawns advisors without end. Original diagram by the authors, created with AI assistance.

Oblivious versus restricted

There is a choice hidden in "find a body match and fire." Should the chase fire every time the body matches, or only when the head is not already satisfied? The two answers are the oblivious chase and the restricted (standard) chase [2], and both live in one branch of the loop (chase.py lines 123-131):

            for h in list(homomorphisms(body, inst)):
                if restricted:
                    if _head_satisfied(head, h, inst):
                        continue
                else:  # oblivious
                    key = (ri, tuple(sorted(h.items())))
                    if key in fired:
                        continue
                    fired.add(key)

The oblivious chase (the else branch) fires each distinct (rule, body-match) trigger exactly once — it never asks whether a witness already exists, it just mints one, remembering the trigger so it does not fire the identical match twice. The restricted chase (the if restricted branch) first calls _head_satisfied and skips the firing when the head already holds. That satisfaction test is itself a homomorphism check (chase.py lines 95-102):

def _head_satisfied(head, h, instance) -> bool:
    grounded = [_apply(atom, h) for atom in head]
    for _ in homomorphisms(grounded, instance):
        return True
    return False

It applies the frontier match h to the head, then searches for any homomorphism binding the remaining existential variables to terms already in the instance. If one exists, a witness is already present and firing would only add a redundant anonymous copy. That single check is the entire difference between a thrifty chase and a wasteful one.

Why it matters on the running example: the seed instance is deliberately lopsided (chase.py lines 186-191). bob already advises the student carol, but alice advises no one. So when the professor rule is tested, _head_satisfied returns True for bob (his advisee-who-is-a-student exists) and False for alice (hers does not). The restricted chase therefore invents a witness only for alice; the oblivious chase mints one for bob too, even though carol was standing right there.

The committed run

Running the companion module chases the four-atom instance both ways and prints the tallies. Here is the real committed output:

Terminating TGD set on a 4-atom instance
  restricted chase: terminated=True, 3 firings, 3 nulls, |result|=10
  oblivious  chase: terminated=True, 5 firings, 5 nulls, |result|=14
  (oblivious mints a witness for bob too, though bob already advises carol)

Both chases terminate, but they land on instances of different sizes:

chase discipline	terminated	firings	nulls minted	result size	witnesses for
restricted (standard)	True	3	3	10	alice only
oblivious	True	5	5	14	alice and bob

The three restricted firings tell the whole story. First, Professor(alice) fires — alice advises no student — minting _n1 and adding advises(alice, _n1) and Student(_n1). Second, Student(carol) fires, minting _n2 for her institution. Third, the invented student _n1 is itself a Student, so the second rule fires again, minting _n3 — a null giving a null an affiliation. Then a full pass adds nothing and the chase halts: $4$ seed atoms plus $6$ new ones equals the $10$ reported. Professor(bob) never fires: _head_satisfied finds carol.

The oblivious chase does all three of those and two more: it fires Professor(bob) (minting _n for a redundant advisee) and then that advisee's affiliation, reaching $5$ firings, $5$ nulls, and $14$ atoms. Both results are universal models — each maps by homomorphism into every model of the TGDs, so both answer conjunctive queries identically [2] — but the restricted chase reaches one that is strictly smaller. When the chase must be materialized, those two extra nulls are exactly the waste a real reasoner works to avoid.

When the chase diverges

Termination was not free; it was a property of these rules. Change the rule so an invented individual re-triggers the very rule that made it, and the chase never stops. The companion's divergent example is one line (chase.py lines 204-208):

NONTERMINATING_INSTANCE = {("Researcher", "alice")}
NONTERMINATING_TGDS = [
    ([("Researcher", "?x")],
     [("advises", "?y", "?x"), ("Researcher", "?y")]),
]

In words: every researcher was advised by some researcher — $\text{Researcher}(x) \rightarrow \exists y.\, \text{advises}(y, x) \wedge \text{Researcher}(y)$. Start with Researcher(alice). The rule fires, minting _n1 — a researcher who advises alice. But _n1 is a Researcher, so the rule fires again, minting _n2 who advises _n1. And _n2 is a researcher, and so on: an infinite regress of anonymous advisors' advisors. The restricted check does not save us here, because each new null genuinely lacks an advisor until the next firing supplies one; the head is never already satisfied. The companion runs this under a max_steps=50 cap so the divergence is visible but bounded:

Non-terminating TGD (Researcher(x) -> ∃y advises(y,x) ∧ Researcher(y))
  terminated=False after the 50-firing cap; 50 fresh advisors invented and still growing

terminated=False is the honest signal: the chase did not reach a fixpoint, it hit the wall. Remove the cap and the loop runs forever. This is not a bug but a genuine feature of existential rules. Chase termination is undecidable in general: no algorithm can inspect an arbitrary TGD set and always correctly decide whether its chase halts [3]. Whole families of rules are therefore studied by the sufficient conditions they satisfy — weak acyclicity, guardedness, and their relatives — each carving out a fragment where the chase is finite, or at least where query answering stays decidable even when it is not [3].

The unsolved part

The uncomfortable question sits right at the divergence. If the chase of a rule set can be infinite — and undecidably so — how can we ever answer a query against it? Materializing the whole model is off the table: there is no whole model to hold. Yet the query "who advises some researcher?" plainly has answers over the researcher ontology, and they should not depend on our inability to finish an infinite construction. Two escapes exist, and neither is free. One restricts the rules to a terminating fragment and pays in expressive power — you give up exactly the cyclic axioms that caused the trouble. The other keeps the expressive rules but never builds the chase, answering queries by rewriting them into a form evaluable directly over the finite input data. Which escape a system takes, and what it costs, is the open engineering tension that organizes the entire field of ontology-based query answering — and no single choice wins on every axis of expressiveness, decidability, and scale at once.

Why it matters

Existential rules are where symbolic reasoning stops merely bookkeeping the individuals it was given and starts positing individuals it was not — the exact expressive step description logic takes with its ∃ constructor, with the chase as its operational meaning: the reason an ontology can entail "alice advises someone" without knowing who. For neuro-symbolic AI the lesson cuts two ways. The chase's invented nulls are a crisp, checkable notion of "an entity the model requires but cannot name" — precisely the latent structure a learned model gropes toward when it hallucinates a plausible-but-unnamed filler, and the chase says exactly when such a filler is warranted. And the undecidability of termination is a hard ceiling no neural approximation repeals; the restricted chase's discipline — fire only when no witness already exists — is exactly the guardrail a learned reasoner needs to avoid inventing witnesses it already has.

Key terms

• Existential rule / tuple-generating dependency (TGD) — a rule body → head whose head may carry existential variables the body never bound; it asserts that something exists without naming it.
• Frontier variable — a variable shared by body and head, carrying a known value across; contrasted with an existential (head-only) variable, the witness to be invented.
• Fresh null — an invented placeholder constant (_n1, _n2, …) standing for a required-but-unnamed individual; distinct from every constant and every other null.
• The chase — forward chaining for TGDs: match the body, and mint a fresh null for each existential variable in the head. Its fixpoint (when it has one) is a universal model.
• Oblivious chase — fires on every distinct body match, always minting a witness; simple but wasteful (five nulls here).
• Restricted (standard) chase — skips a firing when _head_satisfied finds an existing witness; fewer nulls (three here) and it terminates on more inputs.
• Universal model — a model that maps by homomorphism into every model, so conjunctive queries answered over it are answered over all models.
• Chase termination — whether the chase halts; undecidable in general, studied through sufficient fragments (weak acyclicity, guardedness).

Where this leads

The chase hands us a universal model — but sometimes an infinite or impractically huge one, so we cannot always hold it in memory to query it. The next chapter, Certain Answers, closes that gap: it defines a query's certain answers as the tuples true in every model, shows they are exactly the null-free answers read off the chase, and — crucially — explains how to obtain them without materializing the chase whole, so that even a divergent rule set like the researcher regress can still return the finite, certain truths a query asks for.