Query Embedding: The Computation DAG

📍 Where we are: Part V · Complex Logical Query Answering — Chapter 15. RNNLogic and the Symbolic Baseline AnyBURL closed the rule-learning arc: machinery that predicts one missing edge at a time. This chapter opens Part V by asking a whole first-order question at once, and by building the exact symbolic instrument every neural model in this Part will be scored against.

Volume 3 posed one kind of question to the academic world: given the pair (bob, advises), which tail entity completes the triple? Part IV learned rules that answer it. But the questions people actually ask a knowledge graph are rarely single edges. "Who is advised by an advisee of alice but not advised by carol?" is one question, yet it touches three edges, quantifies over an intermediate person, and contains a negation. Answering it is complex logical query answering (CLQA), and the entire field rests on one representation: the query rewritten as a small directed graph of set operations, executed from the leaves up. This chapter builds that representation, the canonical taxonomy of 14 query shapes, an exact executor that answers each shape over any edge set, and the evaluation protocol, defined by the benchmark this chapter reenacts at toy scale (BetaE, short for Beta Embeddings, a name that recurs in the committed code below and returns as a model in the next chapter) [1], that separates answers a model could merely look up from answers it must genuinely infer. Everything runs, and every number is committed, in query_dag.py.

The simple version

Imagine a detective working a case with a stack of transparent sheets, one per clue. "The suspect was advised by one of alice's students": that clue starts at alice, follows the arrow labeled advises twice, and shades every name it reaches. "The suspect is not advised by carol": that clue shades everyone, then erases carol's advisees. Laying the sheets on top of each other and keeping only the names shaded on every sheet is the answer. Now the twist that makes it a research problem: the detective's case file is missing pages. Some arrows that exist in the world were never filed. A suspect reachable only through a missing arrow can never be found by following the file, no matter how carefully; finding that suspect requires guessing the missing arrow correctly. This chapter formalizes the sheets (the computation DAG, a directed acyclic graph of set operations), the overlaying (set intersection, union, complement), and, most importantly, the grading scheme: models are scored only on the suspects the file alone can never reach.

What this chapter covers

• The task, named and bounded: existential first-order queries with one free variable, built from projection, conjunction, disjunction, and a controlled form of negation; what the fragment excludes and why the fragment is the one the field can actually evaluate.
• The computation DAG: anchors at the leaves, four set operators at the internal nodes, evaluation in topological order; one committed query walked node by node with the actual academic-world sets at every step.
• The 14-type taxonomy decoded: the naming grammar behind 1p, 2p, 3p, 2i, 3i, pi, ip, 2u, up, 2in, 3in, inp, pin, pni, the committed 36-query bank's census, and the train-on-five, zero-shot-on-four convention that tests compositional generalization.
• A symbolic executor that audits itself: recursive set evaluation in roughly 30 lines, cross-checked by rewriting every query through De Morgan's law and demanding identical answers, 36 out of 36.
• Easy versus hard, the protocol's core: answers reachable by traversing the training graph versus answers that require imputing a held-out edge; a monotonicity theorem proved by structural induction, its failure under negation witnessed by a committed query, and the filtered ranking metric computed on hard answers only.
• Why answering is not predicting one link: the combinatorial amplification of incompleteness, derived as a product and shown on a committed intersection query whose sole answer hinges on two edges' joint truth.

From one missing edge to a first-order question

Fix the notation once. The academic world is a knowledge graph over the entity set $V$, the 13 individuals of Volume 1's knowledge base (5 people, 3 papers, 2 institutions, 3 topics), and 5 relations (advises, affiliated, authored, about, cites). An edge is a triple $(h, r, t)$: a head entity $h$, a relation name $r$, a tail entity $t$, read "$h$ stands in relation $r$ to $t$". A set of such triples is an edge set $E$; the full academic world is the 18-edge set imported from kg.TRIPLES, never retyped (query_dag.py lines 70–74).

Now the opening question, formalized step by step. "Who is advised by an advisee of alice but not advised by carol?" has one free variable $x$: the slot the answer fills, the person we are looking for. It has one existential variable $y$: the unnamed intermediate advisee, about whom the question claims only that some suitable person exists (the symbol $\exists$ reads "there exists"). And it has three atoms, single relation statements joined by $\wedge$ ("and") with one negated by $\neg$ ("not"):

$$q(x) \;=\; \exists y.\; \underbrace{\text{advises}(\text{alice}, y)}_{\text{atom 1: } y \text{ is alice's advisee}} \;\wedge\; \underbrace{\text{advises}(y, x)}_{\text{atom 2: } y \text{ advises } x} \;\wedge\; \underbrace{\neg\,\text{advises}(\text{carol}, x)}_{\text{atom 3: carol does not advise } x}.$$

The answer set of $q$ over an edge set $E$, written $\llbracket q \rrbracket_E$ (the double brackets read "the meaning of"), is the set of entities that make the formula true when substituted for $x$, with $y$ allowed to range over anything. This query is entry pin[0] of the committed bank (query_dag.py lines 334–337), and its answer over the full 18 edges is the two-element set containing carol and dave: alice advises bob, bob advises both, and carol advises neither.

The fragment this Part works in is built exactly from these ingredients. Existential positive first-order (EPFO) queries allow existential quantification, conjunction, and disjunction $\vee$ ("or"), with a single free variable; the field standardized on nine EPFO shapes [2], later extended by five shapes that add negation applied to one operand of an intersection [1]. Everything else is excluded, and the exclusions are load-bearing. No universal quantification ($\forall$, "for all"): a universally quantified query cannot be answered by following edges outward from named starting entities, because it constrains all neighbors rather than asking for the existence of one. No second free variable: with two free slots the answer is a set of pairs, and the ranking protocol below, which ranks single entities, no longer applies. One further restriction is quieter but equally load-bearing: the field limits itself to queries whose dependency structure is tree-shaped and rooted at named anchor entities. EPFO as defined above also admits cyclic conjunctive queries, in which two existential variables constrain each other in a loop; those cannot be evaluated from the leaves up at all, and their evaluation is NP-hard (NP, short for nondeterministic polynomial time, is the class of problems whose candidate answers can be checked in polynomial time; NP-hard means at least as hard as everything in that class) when the query counts as part of the input (a classical result: no polynomial-time algorithm exists for the general problem unless P = NP, the widely-conjectured-false equality of the class P, the problems solvable in polynomial time, with NP; any single fixed query still evaluates in time polynomial in the data) [3]. We return to what lies beyond the fragment at the chapter's end; within it, two properties hold that the whole methodology depends on. Every query in the tree-shaped, anchored fragment can be answered exactly by polynomial-time set operations over a known edge set (this section's executor), and every intermediate result is a set of entities, which is precisely the kind of object an embedding model can hope to represent as one region of vector space (the next chapter's move).

The computation DAG: four operators, evaluated leaves-up

The load-bearing representation converts the formula into a query computation DAG: a directed acyclic graph whose leaves are anchor entities (the constants named in the query: alice, carol) and whose internal nodes are set operators, evaluated in topological order, meaning every node is computed only after all nodes feeding into it [4]. Four operators suffice for the whole fragment. Each consumes one or more sets of entities and produces one. Two symbols in the semantics column deserve a decode before they appear: $\in$ reads "is a member of", and the brace-and-bar pattern $\lbrace t \mid \ldots \rbrace$ reads "the set of all $t$ such that the condition after the bar holds" (a colon used inside the braces, or after $\exists$, reads the same way: "such that"). Here are the exact semantics, with $S$ an input set, $r$ a relation, and $S_1, \dots, S_m$ operand sets (the count $m$ is the node's number of incoming branches):

operator	plain reading	set semantics	code
anchor $e$	"start at entity $e$"	$\lbrace e \rbrace$	query_dag.py lines 139–141
projection $P_r$	"follow relation $r$ one hop from everything in $S$"	$P_r(S) = \lbrace t \mid \exists h \in S : (h, r, t) \in E \rbrace$	lines 121–124
intersection	"keep what every branch found"	$S_1 \cap \cdots \cap S_m$	lines 152–157
union	"pool what any branch found"	$S_1 \cup \cdots \cup S_m$	lines 142–144
negation	"everything except $S$"	$V \setminus S$ (the complement within the 13 entities)	line 150

One honesty note belongs to the negation row before anything is built on it. Reading $\neg$ as the complement $V \setminus S$ is a closed-world convention: it treats every statement not derivable from the edge set as false, which is defensible over 13 entities we enumerated ourselves and far harder to defend over a real knowledge graph whose absent edges are merely unrecorded. The field's benchmark adopts exactly this reading (its distribution-based negation approximates the complement; our executor computes it outright), so the toy inherits the convention rather than inventing it [1]. It is a convention, and the final section returns to it.

The opening query's DAG has seven nodes, counting each operator as its own node. Two anchors sit at the leaves. Above alice, a chain of two projections implements atoms 1 and 2: from $\lbrace\text{alice}\rbrace$, follow advises to get alice's advisees, then follow advises again to get their advisees. Above carol, one projection followed by a complement implements atom 3: carol's advisees, then everyone else. A final intersection node meets the two branches, and its output is $\llbracket q \rrbracket_E$. The existential variable $y$ never appears as a node: it is absorbed into the projection, which quantifies over intermediates by construction (its semantics already says "there exists an $h$ in $S$"). That absorption is the whole trick; it is why an infinite-seeming logical search becomes a finite pipeline of set operations. (One bookkeeping convention to fix now: the committed executor stores each run of consecutive projections and complements as a single chain node, so its tuple for this query has five nodes, two anchors, two chains, one intersection. The printed trees below draw chains the same way.)

One committed query as its computation DAG, evaluated leaves-up with real sets at every node, beside the two-graph protocol that defines which of its answers count as hard. Original diagram by the authors, created with AI assistance.

The executor that evaluates any such DAG is 31 lines of recursive Python (plus the two small helpers _project and _is_chain), and it is worth reading in full because the next four chapters replace each of its branches with a neural counterpart (query_dag.py lines 127–157):

def eval_query(q, edges: frozenset[tuple[str, str, str]]) -> frozenset[str]:
    """The exact answer set ⟦q⟧ of a query DAG over ``edges``.

    Node grammar (nested tuples, BetaE's data convention):
      * anchor          — an entity name (a plain string);
      * projection      — ``(sub, (t1, ..., tk))``: evaluate ``sub``, then
                          apply each token left to right, where a relation
                          name r maps S ↦ P_r(S) and the marker N maps
                          S ↦ V − S (closed-world complement);
      * union           — ``(q1, ..., qm, U)``: ⟦q1⟧ ∪ ... ∪ ⟦qm⟧;
      * intersection    — any other tuple ``(q1, ..., qm)``: ⟦q1⟧ ∩ ... ∩ ⟦qm⟧.
    """
    # Anchor: ⟦e⟧ = {e}.
    if isinstance(q, str):
        return frozenset({q})
    # Union node: ⟦(q1,...,qm,U)⟧ = ∪_i ⟦qi⟧.
    if q[-1] == U:
        return frozenset().union(*(eval_query(sub, edges) for sub in q[:-1]))
    # Projection node: fold the chain over ⟦sub⟧.
    if _is_chain(q):
        S = eval_query(q[0], edges)
        for tok in q[1]:
            # N: S ↦ V − S (complement).  r: S ↦ P_r(S) (projection).
            S = (V - S) if tok == N else _project(S, tok, edges)
        return S
    # Intersection node: ⟦(q1,...,qm)⟧ = ∩_i ⟦qi⟧.
    sets = [eval_query(sub, edges) for sub in q]
    out = sets[0]
    for s in sets[1:]:
        out &= s
    return out

Run on the full graph, here is a committed walk of a six-operator DAG (five nodes in the executor's chain form), the negation family's worked example, with the executor's real sets printed at the end (the committed demo prints one such walk per query family; this is the [2] block of the run):

  negation (2in):  q(x) = advises(bob,x) ∧ ¬advises(carol,x)
    intersect ∩
    ├─ chain: project advises
    │  └─ anchor bob
    └─ chain: project advises ▸ ¬ complement
       └─ anchor carol
    EASY = ['carol']   ALL = ['carol', 'dave']   HARD = ['dave']

Walk it node by node on the 18-edge graph. Anchor bob evaluates to the set containing bob alone. Projecting along advises collects every tail of an advises edge whose head is bob: carol and dave. On the other branch, anchor carol projects to the set containing erin (carol advises erin, nothing else), and the complement swaps that for the other 12 entities, everyone but erin. The intersection keeps what both branches agree on: carol and dave, since neither is erin. Every set at every node is small, explicit, and checkable by eye; the EASY, ALL, and HARD labels on the last line are the protocol this chapter is building toward, and they get their own section below.

Fourteen shapes, one naming grammar

The field does not evaluate on arbitrary formulas; it evaluates on 14 canonical DAG shapes, and their names follow a compact grammar worth decoding once so that every later table reads itself. A leading digit counts repetitions of the operation that follows: hops for p, branches for i and u. The letter p is one projection hop; i is an intersection; u is a union; n marks a negation attached to one operand of an intersection. Letters read in composition order. So 2p is two projection hops in a chain; 3i intersects three one-hop branches; pi feeds a two-hop projection and a one-hop branch into an intersection; ip inverts that order, intersecting first and projecting from the result; up projects one hop out of a union; and pni is an intersection whose negated operand is the two-hop chain (contrast pin, where the negation sits on the one-hop operand). The committed bank instantiates each shape two or three times over the academic world, 36 queries in all (query_dag.py lines 221–351), and the run prints the census, with each type's structure in the benchmark's own template notation, where e is an anchor, r a relation, n the negation marker, and u the union marker:

[1] the 14 canonical query types (taxonomy of the bank)
  type  structure                          #q  #easy  #hard
  1p    (e,(r,))                            3      2      2
  2p    (e,(r,r))                           3      2      2
  3p    (e,(r,r,r))                         3      2      2
  2i    ((e,(r,)),(e,(r,)))                 3      1      2
  3i    ((e,(r,)),(e,(r,)),(e,(r,)))        2      0      2
  pi    ((e,(r,r)),(e,(r,)))                3      2      2
  ip    (((e,(r,)),(e,(r,))),(r,))          2      1      1
  2u    ((e,(r,)),(e,(r,)),(u,))            3      5      2
  up    (((e,(r,)),(e,(r,)),(u,)),(r,))     3      4      2
  2in   ((e,(r,)),(e,(r,n)))                3      2      2
  3in   ((e,(r,)),(e,(r,)),(e,(r,n)))       2      1      1
  inp   (((e,(r,)),(e,(r,n))),(r,))         2      2      1
  pin   ((e,(r,r)),(e,(r,n)))               2      2      1
  pni   ((e,(r,r,n)),(e,(r,)))              2      2      1
  all                                      36     28     23
  every one of the 14 types has ≥1 query with a nonempty HARD set (14/14)

The 1p row is Volume 3 exactly: one anchor, one hop, one missing tail. Everything below it is the growth this Part studies. Notice also what the census is for: the #easy and #hard columns are the protocol's bookkeeping, and the closing line is a designed property of the bank, since a type with no hard answers would silently vanish from every metric.

One convention rides on this taxonomy, and it is the protocol's sharpest idea, stated here once for the whole Part. Models are trained on queries of types 1p, 2p, 3p, 2i, and 3i (plus the negation types, for models that support negation [1]) and then evaluated on ip, pi, 2u, and up, types they have never seen a single instance of [2]. This is not a data split; it is a structure split. A model that answers up queries after training only on chains and intersections must have learned projection, intersection, and union as composable operators rather than memorizing query templates: zero-shot compositional generalization, tested by construction. When the next chapters report per-type numbers, the held-out columns are the ones to watch.

The executor audits itself: De Morgan as a cross-check

A ground-truth instrument that might itself be buggy is worthless, so the committed module cross-examines its executor with an identity from Boolean algebra. De Morgan's law states that an intersection can be computed without ever intersecting:

$$S_1 \cap S_2 \cap \cdots \cap S_m \;=\; V \setminus \big( (V \setminus S_1) \cup (V \setminus S_2) \cup \cdots \cup (V \setminus S_m) \big).$$

The proof is four elementary steps. An entity $x$ belongs to the left side exactly when it belongs to every $S_i$. That holds exactly when there is no index $i$ with $x \in V \setminus S_i$, which holds exactly when $x$ lies outside the union of the complements, which is the right side's membership condition. Each step is a definition unfolding; nothing else is used.

The cross-check (query_dag.py lines 170–195 and 531–551) rewrites every intersection node of every query in the bank into the complement-of-union-of-complements form, runs the same executor on the rewritten DAG, and asserts the two answer sets are identical on both graphs; a mirror rewrite dissolves every union node the same way, which is exactly the benchmark's own alternative evaluation mode for its union types [1]. The two routes compute the same sets through different operator code, so agreement is evidence against a bug in either. The committed run:

[4] De Morgan cross-check — two independent evaluation routes
  ∩ as ¬(∪¬)  : 36/36 queries agree on G_train and G_full (21 rewrites non-identity, incl. all 11 negation queries)
  ∪ as ¬(∩¬)  : 36/36 agree (6 union queries — BetaE's --evaluate_union DM mode)

The parenthetical counts guard against a vacuous pass: 21 of the 36 rewrites actually changed the DAG (the nine pure projection chains and the six union-only 2u/up queries have no intersection node to rewrite, and 36 − 9 − 6 = 21), and all 11 negation queries are among them, so the agreement is earned, not trivial. The module asserts both counts (query_dag.py line 551).

Easy versus hard: the protocol's core

Now the two graphs. Volume 3's chapter on the ranking protocol fixed a deterministic split of the 18 edges: 15 training edges ($G_{\text{train}}$, from kg.TRAIN) and 3 held-out test edges, chosen so every entity and relation still occurs in training (kg.py lines 65–74). The held-out three are (bob, advises, dave), (bob, authored, p1), and (erin, affiliated, cmu). Write $G_{\text{full}}$ for all 18. Since $G_{\text{train}} \subset G_{\text{full}}$ (the symbol $\subset$ reads "is a proper subset of"), every query can be evaluated on both, and the protocol's three sets are one subtraction apart (query_dag.py lines 200–213):

$$\text{EASY}(q) = \llbracket q \rrbracket_{G_{\text{train}}}, \qquad \text{ALL}(q) = \llbracket q \rrbracket_{G_{\text{full}}}, \qquad \text{HARD}(q) = \text{ALL}(q) \setminus \text{EASY}(q).$$

An easy answer is reachable by traversing edges the model was trained on: producing it requires no generalization whatsoever, only lookup. A hard answer requires at least one held-out edge, so no amount of traversal over the training graph can find it; a model that finds it has genuinely inferred a missing edge in the right place in a multi-step computation [1]. Rerun the worked 2in query above on the training graph: bob's advises projection now yields only carol, because (bob, advises, dave) is held out, and the intersection shrinks to carol alone. EASY is the set containing carol; ALL contains carol and dave; HARD is dave, and dave is hard precisely because the one edge that reaches him is one of the three held out. Across the bank, the census already showed the totals: 28 easy answers, 23 hard ones, every type represented. One toy-scale compression must be disclosed here: the real benchmark nests three graphs (train, then train plus validation, then all edges) and computes a test query's easy answers on the middle one; our two-graph split collapses validation into training, so EASY plays the role of the validation-graph answer set, and query_dag.py states this simplification plainly in its docstring (lines 30–34).

For queries without negation, the easy set can never overflow the all set, and this deserves a proof rather than a shrug because the proof shows exactly where negation breaks it. Claim: if a query $q$ contains no negation, then $E \subseteq E'$ (the symbol $\subseteq$ reads "is a subset of, equality allowed", in contrast to the strict $\subset$ above) implies $\llbracket q \rrbracket_E \subseteq \llbracket q \rrbracket_{E'}$ (adding edges only adds answers; evaluation is monotone). The proof is structural induction over the DAG, strengthened to track the input sets: we show each operator's output grows, in the subset sense, when both its input sets and the edge set grow. An anchor evaluates to $\lbrace e \rbrace$ regardless of edges: monotone. For projection, write $P_r(S, E)$ for the table's $P_r(S)$ computed over edge set $E$, making explicit the edge set the table left implicit; now suppose $S \subseteq S'$ and $E \subseteq E'$, and take any $t \in P_r(S, E)$. By the semantics there is a witness $h \in S$ with $(h, r, t) \in E$. That same $h$ lies in $S'$ and that same triple lies in $E'$, so $t \in P_r(S', E')$: monotone in both arguments. For intersection and union, if $S_i \subseteq S_i'$ for every operand $i$, then any $x$ in every $S_i$ (respectively, in some $S_i$) is in every $S_i'$ (in some $S_i'$): both monotone. Induction from the leaves up carries the property to the root. Now watch the complement refuse to cooperate: $S \subseteq S'$ gives $V \setminus S' \subseteq V \setminus S$, the reverse inclusion. One negation node flips the direction of growth, and the induction dies there. The committed run both asserts the theorem for all 25 negation-free queries and exhibits the failure with a designed witness (query_dag.py lines 553–565):

[3] negation breaks monotonicity (why BetaE's protocol filters with care)
  q(x) = affiliated(dave,x) ∧ ¬affiliated(erin,x)   [2in]
    on G_train : ['cmu']  (erin's cmu edge is held out, so ¬ lets cmu through)
    on G_full  : []  (the held-out edge RETRACTS the answer)
  for ¬-free queries EASY ⊆ ALL always holds (asserted for all 25 EPFO queries)

On the training graph, erin appears unaffiliated, the complement admits cmu, and the query answers cmu; the full graph reveals erin's cmu affiliation and the answer is retracted. A training-graph "answer" to a negation query can be an artifact of missing edges, which is why the protocol defines correctness against $G_{\text{full}}$ alone; for negation queries the training-graph evaluation is not even a lower bound, it can assert answers the full graph refutes.

Metrics on hard answers only, filtered

Scoring is Volume 3's filtered ranking, upgraded for sets. A scoring model is any function $s(q, e)$ assigning a plausibility scalar to entity $e$ as an answer to query $q$; higher means more plausible. For each hard answer $v$ of each query, the model ranks $v$ against the non-answers $V \setminus \text{ALL}(q)$: every other true answer, easy or hard, is removed from the candidate list first, exactly the "filtered" convention of Volume 3's ranking-protocol chapter, so that a model is never punished for ranking one correct answer above another [1]. One hardening is new here (query_dag.py lines 367–388): ties contribute their expected rank under uniform tie-breaking,

$$\text{rank}(v) \;=\; 1 \;+\; \#\lbrace e : s(q,e) \gt s(q,v) \rbrace \;+\; \tfrac{1}{2}\,\#\lbrace e : s(q,e) = s(q,v) \rbrace,$$

where $\#$ counts a set's elements over the non-answer candidates. Under Volume 3's optimistic convention a constant scorer would tie with everything and claim rank 1; the expected-rank convention makes a plateau of $k$ tied candidates cost $k/2$ places, which matters because CLQA scorers produce exactly such plateaus. The metric is then the filtered mean reciprocal rank (MRR), the average of $1/\text{rank}$ over all 23 hard answers in the bank (query_dag.py lines 391–408).

The committed harness runs three reference scorers that pin down the scale (query_dag.py lines 413–437). The oracle scores 1 if $e \in \text{ALL}(q)$ and 0 otherwise: every hard answer strictly outscores every non-answer, rank exactly 1, MRR exactly 1.0000, the ceiling. The traversal baseline scores 1 if $e \in \text{EASY}(q)$ and 0 otherwise: it is the ceiling of any system that treats the training graph as complete, the strongest pure lookup that graph supports, and it scores 0 on every hard answer by the definition $\text{HARD} = \text{ALL} \setminus \text{EASY}$. (A symbolic rule learner is not bound by this zero: the previous chapter's AnyBURL mines rules from the training graph that impute held-out edges, so it can put a hard answer at rank 1. Only literal lookup is shut out by construction.) A frozen random scorer (seed 0) gives the uninformed floor. The run:

[5] filtered MRR over the 23 hard answers (rank vs non-answers V − ALL; ties → expected rank)
  type   #hard   oracle  traversal  random(0)
  1p         2   1.0000     0.1484     0.2250
  2p         2   1.0000     0.1484     0.1010
  3p         2   1.0000     0.1484     0.4167
  2i         2   1.0000     0.1429     0.1125
  3i         2   1.0000     0.1429     0.0909
  pi         2   1.0000     0.1484     0.5625
  ip         1   1.0000     0.1429     0.1000
  2u         2   1.0000     0.1603     0.1056
  up         2   1.0000     0.1538     0.2917
  2in        2   1.0000     0.1484     0.1964
  3in        1   1.0000     0.1429     0.2500
  inp        1   1.0000     0.1538     0.0909
  pin        1   1.0000     0.1538     0.1250
  pni        1   1.0000     0.1538     0.1250
  pooled    23   1.0000     0.1491     0.2128

The traversal column deserves a full derivation, because its numbers are forced, not fitted. Take the 1p row, which pools two hard answers. For the query advises(bob, $x$): ALL contains carol and dave, so 11 of the 13 entities are non-answers; traversal scores the hard answer dave 0, and every non-answer also 0 (a non-answer cannot be easy for this negation-free query, since EASY ⊆ ALL by the monotonicity theorem). Eleven ties give expected rank $1 + 0 + 11/2 = 6.5$, reciprocal $1/6.5 = 0.153846$. For authored(bob, $x$): ALL is the single paper p1, so 12 non-answers tie, rank $1 + 12/2 = 7$, reciprocal $0.142857$. Their mean is $0.148352$, which rounds to the committed 0.1484. Every entry in the column is this same arithmetic; the pooled 0.1491 versus the oracle's 1.0000 is the incompleteness gap, expressed as a number, that a neural model must close. Note also the random column beating traversal in several rows (0.2128 pooled): with only a dozen candidates, blind luck sometimes lands a hard answer high, while traversal never does. Traversal is not a weak model being lazy; it is structurally shut out.

Why answering is not predicting one link

It is tempting to file CLQA under "link prediction, repeated." The intersection queries show why that undersells it. Consider the committed 2i query 2i[0] (query_dag.py lines 250–251):

$$q(x) \;=\; \text{authored}(\text{alice}, x) \,\wedge\, \text{authored}(\text{bob}, x).$$

Each conjunct alone is a perfectly solvable 1p query: on the full graph, alice's authored projection contains p1, and so does bob's. But the conjunction's sole answer p1 depends on the joint truth of two specific edges, (alice, authored, p1) and (bob, authored, p1). The training graph contains the first and holds out the second, so traversal's intersection is empty: EASY is the empty set, HARD is p1. To produce p1 a model must simultaneously trust an observed edge and impute a missing one, and a single wrong call on either conjunct destroys the answer.

The amplification generalizes, and a two-line probability sketch makes the trend exact. Suppose, as an idealization, each true edge survives into the training graph independently with probability $p$ (the retention rate; here $15/18 = 5/6 \approx 0.833$, though the committed split is deterministic rather than sampled, so the calculation illustrates the mechanism, not the bank's exact counts). An answer whose derivation uses $k$ distinct edges, where $k$ counts the atoms a particular answer needs (2 for a 2i answer, 3 for a 3i or 3p answer), is traversal-reachable only if all $k$ survived, an event of probability

$$p^{k} \quad\text{: with } p = \tfrac{5}{6}, \qquad p^1 \approx 0.833, \qquad p^2 \approx 0.694, \qquad p^3 \approx 0.579.$$

The failure probability $1 - p^k$ grows with every hop and every conjunct, so the deeper and wider the query, the larger the fraction of its true answers that traversal cannot see. Link prediction faces $1 - p$ once; CLQA compounds it. This is the quantitative sense in which the task is link prediction grown up: the same incompleteness, amplified through composition, with the DAG dictating exactly which edges must be jointly right.

Thirteen entities versus fifteen thousand

Why can an executor of roughly 30 lines serve as this Part's gold standard? Count its work. A DAG with $m$ operator nodes evaluates in topological order; each projection scans the edge set once ($|E|$ triples, with $|\cdot|$ denoting a set's size), each complement touches at most $|V|$ entities, and each intersection or union merges sets no larger than $|V|$. Total cost $O\!\big(m \cdot (|E| + |V|)\big)$, where $O(\cdot)$ reads "grows at most proportionally to": for 36 queries over 18 edges and 13 entities, microseconds. At toy scale, exhaustive exact evaluation is cheap, and that is precisely why the toy is useful: every neural number reported in the next three chapters can be compared against a perfect answer key, per query, per entity.

At benchmark scale the same arithmetic explains the field's predicament. The standard benchmarks pose these query types over graphs with tens of thousands of entities and hundreds of thousands of edges, with query banks sampled in the millions; a single projection from a large intermediate set is already a ranking problem over the whole entity vocabulary, intermediate sets can blow up to thousands of entities mid-query, and the executor's per-node exactness stops being free [5]. More fundamentally, no matter how much compute is spent, traversal of the observed graph remains the baseline that cannot find hard answers: its zero on the hard set is definitional, at every scale, which is the field's standing argument for embedding queries rather than executing them [1]. The committed toy makes that argument a reproducible table rather than a slogan; the survey's map of the field is, in large part, a catalog of ways to beat the 0.1491 column without giving up the DAG [5].

The unsolved part

Everything in this chapter is a convention wearing the costume of a law, and it is honest to take the costume off. Closed-world negation is the loudest case: reading ¬ as the complement of 13 entities we enumerated ourselves is defensible; reading it as the complement of a web-scale graph's recorded edges asserts that every unrecorded affiliation is false, which is exactly the incompleteness assumption the rest of the protocol exists to reject. The witness query above showed the symptom in miniature, an answer asserted and then retracted as edges arrived. The single-free-variable restriction is the second case: the moment a question binds two unknowns at once ("which advisor and student pairs co-authored a paper?") the answer is a set of tuples, the DAG's one-region-per-node picture no longer fits, and cyclic query graphs, where two variables constrain each other, escape leaves-up evaluation entirely; extending evaluation beyond the tree-shaped, one-variable fragment is an explicit and active frontier [6]. And beneath both sits the benchmark-design lesson Volume 3 taught for link prediction: the query bank's distribution, which structures are sampled, which anchors, which relations, silently shapes every reported number. Our bank is hand-chosen so that all 14 types have hard answers; a sampled bank makes thousands of such choices invisibly, and no MRR table announces them.

Why it matters

The DAG is the hinge on which this entire Part turns. The remaining chapters of this Part will replace the executor's set operations with geometric and probabilistic counterparts (regions for sets, learned operators for projection and intersection), and every one of those models will be trained on the five-type split, scored on the 23 hard answers, and compared against the two reference columns established here: the oracle's 1.0000 and traversal's 0.1491. Nothing about that evaluation is neural; it is a symbolic instrument, cross-checked through De Morgan, and its exactness at toy scale is what will let us say precisely where a neural query answerer succeeds and where it fails. The chapter also pays forward to Volume 5: the easy/hard split is this field's version of the question "did the model reason, or did it look up?", and the zero-shot structure split is its version of "did the model learn operators, or templates?". Both questions return, at much higher stakes, when the reasoner is a language model.

Key terms

• Complex logical query answering (CLQA) — answering first-order queries with existential quantification, conjunction, disjunction, and limited negation over an incomplete knowledge graph; link prediction is its one-atom special case.
• EPFO query — an existential positive first-order query: one free variable, existential variables, ∧ and ∨, no negation; the nine positive canonical types [2], extended by five negation types [1].
• Query computation DAG — the query as a directed acyclic graph: anchor entities at the leaves, set operators at the internal nodes (projection and intersection from [4], union from [2], complement from [1]), evaluated in topological order; the existential variable is absorbed into projection.
• Relation projection — $P_r(S) = \lbrace t \mid \exists h \in S : (h,r,t) \in E \rbrace$, the one-hop image of a set; the only operator that reads the edge set.
• Closed-world negation — reading ¬ as the complement $V \setminus S$ within the known entity set; the field's convention, inherited here, and a convention rather than a truth about missing edges.
• Easy / hard answers — $\text{EASY} = \llbracket q \rrbracket_{G_{\text{train}}}$, $\text{ALL} = \llbracket q \rrbracket_{G_{\text{full}}}$, $\text{HARD} = \text{ALL} \setminus \text{EASY}$; hard answers require imputing at least one held-out edge, and metrics are computed on hard answers only.
• Monotonicity — for negation-free queries, adding edges only adds answers (proved by structural induction); one complement node breaks it, witnessed by the committed retraction query.
• Filtered MRR with expected-rank ties — mean reciprocal rank against the non-answers $V \setminus \text{ALL}$, other true answers filtered out, ties charged half their plateau; oracle 1.0000, traversal 0.1491, random 0.2128 on the committed bank.
• Zero-shot structure split — train on 1p, 2p, 3p, 2i, 3i (plus negation types [1]), evaluate on unseen ip, pi, 2u, up: compositional generalization tested by construction [2].

Where this leads

The instrument is built; now come the players. The next chapter, From GQE to BetaE, makes the DAG differentiable: anchor nodes become entity embeddings, projection becomes a learned transformation, intersection becomes an operation on regions (a point, then a box, then a Beta distribution), and the executor's exact sets become geometries trained to approximate them. The three columns of this chapter's MRR table are waiting for a fourth: a model that beats 0.1491 by actually inferring the held-out edges, scored on the same 23 hard answers by the same filtered protocol.

---

Companion code: examples/integration/query_dag.py implements this entire chapter: the two graphs and the closed world (lines 70–74), the 14 structures (lines 84–99), the executor (lines 112–157), the De Morgan rewrites and their 36/36 cross-check (lines 160–195 and 531–551), the easy/hard protocol (lines 198–213), the 36-query bank with per-query first-order readings (lines 216–351), the filtered-rank and MRR harness (lines 365–408), the three reference scorers (lines 411–437), and the asserts guarding every claim made here, including the monotonicity theorem and the non-monotone witness (lines 501–588). Run python3 examples/integration/query_dag.py to reproduce every number byte for byte; the run ends with SUMMARY query_dag: types=14 queries=36 hard=23 hard_types=14 demorgan=36/36 oracle_mrr=1.0000 traversal_mrr=0.1491 random_mrr=0.2128.