Skip to content
Embabel Worlds

5.12 Bounded variable-length traversal — self-recursive joins

A virtual join whose anchor and target are the same type (an ownership registry’s Company -[:OWNED_BY]-> Company, a stud book’s Pony -[:HAS_PARENT]-> Pony) may be traversed with a variable-length pattern:

MATCH p=(c:Company {companyNumber:'X'})-[:OWNED_BY*1..6]->(o:Company)
RETURN o.companyNumber, [r IN relationships(p) | r.sourceId]

Guarantees.

  • Every hop up to the declared bound is resolved before the query evaluates: the traversal composes what the graph already holds with on-demand fetches — a hop already present advances the walk without a fetch, and fetched hops extend past the held data. Convergent paths dedupe to one node.
  • Cycles terminate. A loop’s closing edge appears in results; nothing is fetched twice.
  • A list-valued keyField is its elements at every hop, as it is for a single hop: a person whose childIds lists three children continues the walk three ways. A walk that read the list as one key stopped after the first generation without a warning, because the tree simply appeared to end.
  • Rollups and subtree sweeps (count, sum, generation slices *k..k, path predicates) compose as ordinary Cypher over the resolved tree, and the same rows always yield the same tree.

Costs. The traversal spends against the join’s own declarations, cumulatively across hops: total resolved nodes against maxFanoutTotal, each hop’s frontier width against maxAnchors. An unbounded * is additionally capped at 10 hops.

Degradation. If the walk stops short of the query’s declared depth — budget, frontier width, or the unbounded-* cap — the result carries an INCOMPLETE_TRAVERSAL warning naming the hop reached and the bound hit. Results then cover only the hops walked and any subtree total is a lower bound. Nothing is ever silently truncated; a tree that simply ends, or ends exactly at the declared depth, carries no warning.

Per-hop provenance. Every edge the traversal fetched carries three queryable properties: sourceId (the record’s identity at its source), sourceName (the producer that asserted it), and hop (1-based depth). The result envelope additionally carries one AUDIT_TRAIL note listing every claim — hop N: (from)-[REL]->(to) source=<producer> sourceId=<id> — with hops that were already held in the graph shown as source=mirror. The trail is capped at 500 claims (a count of the remainder is appended).

Limits. A variable-length pattern whose endpoints are different types is not a recursive join and resolves only its first hop. min bounds (*2..) filter results as ordinary Cypher; they do not change what is resolved.

Worked example. With Company {companyNumber identity} OWNED_BY Company declared over an ownership registry, and SC-100 ← SC-220 ← {SC-310, SC-320} ← HOLD-1 at the source, MATCH (c:Company {companyNumber:'SC-100'})-[:OWNED_BY*1..6]->(o) RETURN count(DISTINCT o) answers 4, each OWNED_BY edge cites the registry record that asserted it, and the envelope’s audit trail lists the four claims in hop order.