Certain Answers: Query Answering as Homomorphism

📍 Where we are: Part IV · Datalog and the Chase — Chapter 14. Existential Rules and the Chase built a model by firing rules and minting fresh nulls whenever a head demanded a witness that was not on record; now we ask what that model is for — how to read trustworthy answers off it, and why the reading is the very same operation the chase used to build it.

You have a database that is admittedly incomplete: you know some professors advise some students, but you never claimed to have logged every advising relationship. Someone asks, "who advises a student?" The honest answer is not "whoever my table happens to list." It is "everyone who must advise a student in every state of the world my data allows." This chapter makes that idea exact, shows that a single operation — homomorphism — computes it, and runs it on the academic world to get the answer alice and bob.

The simple version

Imagine a detective with a partial case file. The file does not say who the getaway driver was, only that there was one. A careless assistant might answer "there is no driver" because none is named; a reckless one might guess a name. The detective does neither. She reports only what is true in every story consistent with the file: there exists a driver, but no particular person can be named as the driver with certainty. "There exists a student that alice advises" can be certain even when which student is not. Certain answers are exactly the facts that survive every consistent retelling of the world.

What this chapter covers

• Certain answers, decoded — under the open-world assumption the meaningful answer is not "what is in my data" but "what holds in every world consistent with my data," and why a tuple built from a placeholder null is never certain.
• Homomorphism as the one primitive — a variable assignment that lands every query atom in the instance; this single check is conjunctive-query evaluation and is the chase's satisfaction test.
• Universal models — the chase result maps by homomorphism into every model, so evaluating a query over it, then dropping nulls, yields exactly the certain answers.
• The constants-only filter — certain_answers keeps a tuple only when all its components are constants; query_holds answers a yes/no query by a single homomorphism.
• The committed run — Q(x) :- advises(x, y), Student(y) over the restricted chase returns alice and bob, both professors, with the null-witnessed advisee dropped.
• Datalog versus the chase — Datalog answers are already all constants, so it needs no filter; existential rules add nulls, which is exactly why certainty needs one.

Certain answers, decoded

A relational database, read literally, answers under the closed-world assumption: anything not stated is taken to be false. Ontologies do the opposite. They live under the open-world assumption — what is not stated is unknown, not false — because a knowledge base is deliberately a partial description of a richer reality. Once you accept that, a query has not one world to answer over but many: every model, every full state of affairs $\mathcal{M}$ that satisfies the knowledge base $\mathcal{K}$, is a candidate reality.

Which answers can you trust across all of them? A conjunctive query $Q(\bar{x}) \leftarrow \exists \bar{y}\, \varphi(\bar{x}, \bar{y})$ — a set of atoms $\varphi$ joined by ∧, with some variables $\bar{x}$ reported as the answer and the rest $\bar{y}$ existentially hidden — has, in each model, a set of answer tuples $Q(\mathcal{M})$. The certain answers are the tuples that appear in every model at once [1]:

$$\mathsf{cert}(Q, \mathcal{K}) \;=\; \bigcap_{\mathcal{M}\, \models\, \mathcal{K}} Q(\mathcal{M}).$$

The big ∩ is intersection over all models — a tuple must be an answer in model after model, with no exception, to count. The turnstile $\models$ reads "is a model of / satisfies." This is why a tuple containing a null — a labeled null, a placeholder symbol like _n1 standing for "some individual we cannot name," and pointedly not a constant (in chase.py, is_null("_n1") is true and is_const("_n1") is false; constants and nulls are disjoint) — is never certain. A null is precisely a value the models are free to disagree on: in one model _n1 is carol, in another it is a brand-new person. A tuple that names _n1 is not stable across that disagreement, so it cannot be in the intersection. Only tuples built entirely from genuine constants can be.

Homomorphism: the one primitive

Here is the central economy of this chapter. Two operations that sound different — evaluating a query and testing whether a rule head is already satisfied — are the same operation, and it has a name: a homomorphism. Given a pattern (a list of atoms with ?-variables) and an instance (a set of ground atoms), a homomorphism is an assignment of the pattern's variables to instance terms that lands every pattern atom on some real atom of the instance. In chase.py it is one recursive generator, homomorphisms (lines 57–81):

def homomorphisms(pattern, instance, sub=None):
    """Yield every substitution of the ``?``-variables in ``pattern`` (a list of
    atoms) that maps all of them into ``instance``. This *is* conjunctive-query
    evaluation, and the check the restricted chase uses to test satisfaction."""
    sub = {} if sub is None else sub
    if not pattern:
        yield dict(sub)
        return
    first, rest = pattern[0], pattern[1:]
    for fact in instance:
        if fact[0] != first[0] or len(fact) != len(first):
            continue
        ext = dict(sub)
        ok = True
        for p, f in zip(first[1:], fact[1:]):
            if is_var(p):
                if p in ext and ext[p] != f:
                    ok = False
                    break
                ext[p] = f
            elif p != f:
                ok = False
                break
        if ok:
            yield from homomorphisms(rest, instance, ext)

Read it as the definition made executable. To match the first pattern atom, scan the instance for a fact with the same predicate and arity (fact[0] != first[0] or len(fact) != len(first)); bind each variable position p to the fact's term f, refusing any binding that contradicts one already made (if p in ext and ext[p] != f); when the whole pattern is exhausted (if not pattern), yield the completed substitution. Every yielded sub is one homomorphism. The docstring states the punchline the whole chapter turns on: this is conjunctive-query evaluation [2]. Formally, the answers of $Q$ over an instance $I$ are

$$Q(I) \;=\; \{\, h(\bar{x}) \;:\; h \text{ a homomorphism from } \varphi \text{ into } I \,\}.$$

The same generator, aimed at a rule head instead of a query, is the restricted chase's satisfaction test in _head_satisfied (lines 95–102): "is this head already true?" is just "does the head have a homomorphism into the instance?" One primitive, two jobs — which is why building the model and querying it cost the same kind of work.

The universal model, and why the chase is one

Evaluating over one model is easy; evaluating over all of them sounds impossible, since there are infinitely many. The escape is a single distinguished model that stands in for the whole crowd. An instance $\mathrm{U}$ is a universal model of $\mathcal{K}$ when it satisfies $\mathcal{K}$ and, for every model $\mathcal{M}$ of $\mathcal{K}$, there is a homomorphism from $\mathrm{U}$ into $\mathcal{M}$ that fixes every constant:

$$h : \mathrm{U} \to \mathcal{M}, \qquad h(c) = c \text{ for each constant } c, \qquad \alpha \in \mathrm{U} \;\Rightarrow\; h(\alpha) \in \mathcal{M}.$$

The nulls of $\mathrm{U}$ are the slack: the homomorphism is free to send each null wherever that particular model needs it. A universal model is the "most general" world the data forces — it commits to everything the knowledge base entails and to nothing more. The key theorem of data exchange is that the chase produces exactly such a model, and that certain answers can then be read straight off it by dropping the nulls [1]:

$$\mathsf{cert}(Q, \mathcal{K}) \;=\; Q\big(\mathrm{chase}(\mathcal{K})\big)\big\downarrow_{\text{const}},$$

where $\downarrow_{\text{const}}$ keeps only the constant-only tuples. The proof idea is short and worth holding: any homomorphism witnessing an answer over $\mathrm{U}$ can be pushed forward through $h$ into every model $\mathcal{M}$, so a constant answer over $\mathrm{U}$ is an answer everywhere; and conversely $\mathrm{U}$ is itself a model, so nothing certain can be missing from it. The infinite intersection collapses to one evaluation over one instance.

Computing certain answers: the constants-only filter

The theorem becomes ten lines of code. certain_answers (lines 160–170) evaluates the query over the chased instance and applies exactly the $\downarrow_{\text{const}}$ step:

def certain_answers(query_body, answer_vars, chased_instance):
    """The certain answers to a conjunctive query: evaluate it over the chase
    (a universal model) by homomorphism, then keep only tuples all of whose
    components are *constants* — a null could stand for many different values, so
    a tuple containing one is not certain."""
    answers = set()
    for h in homomorphisms(query_body, chased_instance):
        tup = tuple(h[v] for v in answer_vars)
        if all(is_const(t) for t in tup):
            answers.add(tup)
    return answers

The loop for h in homomorphisms(...) is the query evaluation; if all(is_const(t) for t in tup) is the filter that makes an answer certain rather than merely present. For a yes/no question there is nothing to project and nothing to filter — a boolean conjunctive query is certainly true exactly when one homomorphism exists — which query_holds (lines 173–178) states in three lines:

def query_holds(query_body, chased_instance) -> bool:
    """A boolean conjunctive query is *certainly* true iff it has a homomorphism
    into the chase."""
    for _ in homomorphisms(query_body, chased_instance):
        return True
    return False

To see the filter earn its keep, look at the instance it runs over. The starting ABox has four atoms; bob already advises the student carol, but alice advises nobody yet, so the restricted chase mints a witness only where one is genuinely missing. The result is ten atoms — three firings, three nulls — which the committed run reports and which decompose as follows:

origin	atoms produced	why
the given ABox	Professor(alice), Professor(bob), Student(carol), advises(bob, carol)	the four asserted facts
TGD 1 fires on alice	advises(alice, _n1), Student(_n1)	alice advises nobody, so a fresh null witness is minted
TGD 1 on bob	— (skipped)	bob already advises carol, a real student — head already satisfied
TGD 2 on carol	affiliated(carol, _nᵢ), Institution(_nᵢ)	the real student needs an institution
TGD 2 on _n1	affiliated(_n1, _nⱼ), Institution(_nⱼ)	the invented student is a student too, so it needs one as well

One subtlety about the subscripts: _n1, alice's advisee, is always minted first — TGD 1 fires before TGD 2 — so its index is fixed. The two institution witnesses take the remaining subscripts _n2 and _n3, but which of carol's and _n1's witness gets which index depends on the order Python's set happens to iterate, so _nᵢ and _nⱼ can swap between separate runs. The load-bearing facts never move: ten atoms, three firings, three nulls, and the certain answers below.

The chase over this tuple-generating dependency (TGD) set halts because no invented null loops back to trigger a rule on itself, and the run confirms the count:

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

The committed run: who advises a student?

Now the query. Q_ADVISES_STUDENT is ([("advises", "?x", "?y"), ("Student", "?y")], ["?x"]) — "who advises some student?", reporting the advisor ?x and hiding the advisee ?y. Evaluated over the ten-atom chase, homomorphisms finds exactly two matches, and both project to a constant:

homomorphism $h$	atoms it lands on	answer $h(?x)$	verdict
?x ↦ bob, ?y ↦ carol	advises(bob, carol) ∧ Student(carol)	bob	constant → kept
?x ↦ alice, ?y ↦ _n1	advises(alice, _n1) ∧ Student(_n1)	alice	constant → kept

Both survive the filter, so the certain answers are alice and bob — exactly what the committed run prints:

Certain answers to  Q(x) :- advises(x,y), Student(y)
  ['alice', 'bob']   (both professors — the TGD guarantees each advises some student)
  boolean 'does anyone advise a student?' -> True

Two things are subtle here. First, alice is a certain answer even though no named student is on record as her advisee. The TGD "every professor advises some student" forces the existence of one in every model, and the chase records that forced existence as the null _n1. Because the reported variable is the advisor ?x, whose value alice is a genuine constant, the answer is certain — the uncertainty is quarantined inside the hidden ?y. Second, this is precisely where a null would be dropped. Ask instead for the advisee — project onto ?y — and alice's row yields _n1, a null; the filter discards it, leaving only carol. The existence of alice's advisee is certain; its identity is not. Same chase, same homomorphisms, opposite verdicts, decided entirely by which column the null lands in.

Datalog versus the chase: why the filter is new

It is worth asking why the previous chapters on Datalog never needed a constants-only filter. The reason is structural: Datalog rules can only recombine constants already present — no rule head ever asserts that something new exists — so every atom the least fixpoint derives is built from the constants you started with. Every answer is automatically null-free; the filter would never remove anything, so it is simply absent. Existential rules break that invariant on purpose. The instant a head says $\exists y$, the chase may have to invent a _n-null to satisfy it, and nulls flow into query results. Certainty is what the constants-only filter restores: it is the price of moving from Datalog's closed recombination to the open-world existence claims that ontologies actually need. The homomorphism primitive is unchanged from Datalog evaluation; only the guard at the end is new.

The chase builds one universal model that maps by homomorphism into every consistent world; evaluating the query over it and keeping only constant tuples yields the certain answers alice and bob, while the null-witnessed advisee is filtered away. Original diagram by the authors, created with AI assistance.

The unsolved part

The whole method rests on one word in the theorem: $\mathrm{chase}(\mathcal{K})$. Reading certain answers off a universal model presumes that model can be finished. But the chase need not terminate — swap the terminating rules for "every researcher was advised by some researcher" and each invented advisor is itself a researcher demanding a fresh advisor, an infinite regress. The companion runs exactly this under a step cap:

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

Whether a given TGD set has a finite chase is undecidable in general, and so, in the worst case, is certain-answer computation over unrestricted existential rules [3]. The field's response is not to give up but to carve out fragments where certain answering stays decidable, each by a different escape route: weakly-acyclic sets because the chase is provably finite; sticky sets because a possibly-infinite chase can be side-stepped by rewriting the query into one the raw data answers directly; and guarded sets because the chase, though it may never finish, stays tree-shaped enough — of bounded treewidth — to reason over as it stands. Certain answers are only ever as computable as the universal model behind them, and choosing a rule language is choosing how much of that guarantee you keep.

Why it matters

Certain answers are the honest contract of an open-world reasoner: it returns what must hold, never what merely might, and it says so in a form you can audit atom by atom. For neuro-symbolic AI this is the ground truth a learned component is measured against — a neural link predictor may rank many advisees as plausible, but only alice and bob are entailed, and only the symbolic side can certify the difference. The deeper lesson is the collapse of two tasks into one primitive: query answering and model construction are both homomorphism, so a system that can do one can do the other, and a differentiable relaxation of homomorphism (Volume 4's soft matching) is simultaneously a soft query engine and a soft reasoner. Knowing what the crisp answer is — the exact set alice and bob, filtered free of nulls — is what lets you judge whether the approximation landed on it.

Key terms

• Certain answers — the tuples of constants that answer a query in every model of the knowledge base, $\bigcap_{\mathcal{M} \models \mathcal{K}} Q(\mathcal{M})$; the only answers an open-world reasoner may assert.
• Open-world assumption — unstated facts are unknown, not false; the reason a query ranges over many models rather than one.
• Homomorphism — a variable assignment landing every pattern atom on a real atom of the instance; the single primitive behind both conjunctive-query evaluation and the chase's satisfaction test.
• Conjunctive query — a query $Q(\bar{x}) \leftarrow \exists \bar{y}\, \varphi(\bar{x}, \bar{y})$ whose body is a conjunction of atoms; evaluated by finding homomorphisms of $\varphi$ into the instance.
• Universal model — a model that maps by constant-fixing homomorphism into every other model; the chase produces one, so certain answers reduce to one evaluation over it.
• Null — a labeled null, a placeholder symbol (_n1) for a forced-but-unnamed individual, disjoint from the constants (is_const("_n1") is false); a tuple containing one is never certain, because models fill it differently.
• Constants-only filter — the $\downarrow_{\text{const}}$ step in certain_answers that keeps a tuple only when all components are constants; what turns "present in the chase" into "certain."
• Boolean conjunctive query — a yes/no query, certainly true exactly when one homomorphism into the chase exists (query_holds).

Where this leads

We now have the full open-world pipeline: existential rules build a universal model by the chase, and certain answers are read off it by homomorphism and a nulls-out filter — with the whole guarantee resting on the chase terminating, which in general it may not. Parts I–IV built the theory of what an ontology entails; the next part turns to the machines that decide it fast enough to matter. EL Reasoners opens the study of real systems by returning to the tractable EL family, where the completion-based fixpoint of earlier chapters and the homomorphism-based querying of this one are engineered to run in polynomial time over ontologies with hundreds of thousands of classes. The question shifts from what is entailed to how a reasoner computes it without ever building an infinite model.