Traversal semantics¶

Architecture

Traversal is the operator behind the query language's expand clause: a bounded, temporally-correct, deterministic breadth-first walk of the graph from a set of root nodes, out to 1, 2, or 3 hops.

Overview & purpose¶

Traversal::expand answers "what is reachable from these nodes, as of this bitemporal coordinate, without reading an unbounded amount of the graph." It is the engine-level primitive underneath the query executor's expand stage described in the query language, and it is the operator the PRD's "sub-millisecond 1-3 hop on 10M+ nodes" gate (F6) is measured against (spec §1).

Three problems make this harder than a textbook BFS (spec §2):

• Supernodes. A single high-degree node can turn a 3-hop query into millions of row reads. Left unbounded, traversal becomes a denial-of-service primitive against the engine itself.
• Time-travel paradoxes. Without per-hop temporal filtering, a traversal could follow an edge, or land on a node, that did not exist at the queried coordinate.
• Nondeterminism. Unordered expansion breaks pagination and makes the tombstone-cascade invariants (I1/I2, see Tombstone cascade) untestable, because "byte-identical results across runs" stops being checkable.

The solution is BFS with hard depth bounds, per-hop dual validation of edges and target nodes, visited/used-edge dedupe sets, a multi-dimensional work budget, and a fixed ordering rule at every step (spec §3).

Design¶

Why BFS, not DFS. The spec rejects DFS explicitly (spec §9): BFS visits nodes in strictly increasing hop order, so the first time a node is reached is guaranteed to be via its shortest path from any root. This matters for two reasons at once: it is what makes the visited-set dedupe correct without extra bookkeeping (a node reached a second time via a longer path is just skipped), and it is what the confidence decay model requires, since a node's score must come from its nearest path, not an arbitrary one found by a depth-first walk.

Why depth is capped at 3. The PRD scopes graph queries to 1 to 3 hops, and ExpandSpec::depth is a u8 validated against 1..=3 before any work begins. The spec (§9) treats deeper traversal as a different problem: "deeper traversal wants a different algorithm class, revisit in Phase 4." Depth 0 and depth > 3 are both rejected. The query language enforces the same ceiling one layer up, at parse time, so malformed requests fail before reaching the engine (see Query language › Expand).

Why dual validation of the edge AND the target node. Validating only the edge version is not enough to avoid "dangling hops": an edge can be valid at the query coordinate while the node it points to has since been tombstoned, corrected out of existence, or not yet exist at that coordinate. expand therefore checks two independent things before accepting a hop: the specific EdgeVersion row scanned must have valid_time and tx_time intervals that both contain the queried coordinate, and the neighbor node must resolve to Some(_) under NodeReads::get_as_of at the same coordinate. Either check failing means the hop is silently skipped, not attached with missing data (spec §4, code lines 310-345 of traversal.rs).

Why BFS instead of a denylist for supernodes. The spec considered and rejected maintaining a supernode denylist (§9): budgets already bound the damage a high-fan-out node can do, and a denylist adds hidden state and surprising behavior (a node that works in one query and silently drops edges in another). The budget guard is the only defense against supernodes in v1.

Data model¶

Request shape¶

/// Traversal direction.
pub enum ExpandDirection { Out, In, Both }

/// What to expand (spec §6).
pub struct ExpandSpec {
    /// Restrict to these edge types; `None` = all types.
    pub edge_types: Option<Vec<String>>,
    /// Direction to follow.
    pub direction: ExpandDirection,
    /// Hop depth, 1..=3 (hard cap in v1).
    pub depth: u8,
}

Traversal::expand takes an ExpandSpec plus the root set, the bitemporal coordinate, and a Budget:

pub fn expand(
    &self,
    scope: &TenantScope,
    roots: &[Uuid],
    spec: &ExpandSpec,
    valid_t: Ts,
    tx_t: Ts,
    budget: Budget,
) -> Result<Expansion, TraversalError>

Budget¶

/// Work bounds (spec §6 defaults).
pub struct Budget {
    /// Max accepted neighbors per node per hop.
    pub max_fanout_per_node: u32,
    /// Max total nodes emitted.
    pub max_total_nodes: u32,
    /// Max adjacency rows scanned overall.
    pub max_rows_scanned: u64,
}

Budget implements Default with exactly these three values (traversal.rs lines 80-88). Both-direction expansion (ExpandDirection::Both) counts rows from both the out and in adjacency scans against the same shared budget; there is no separate allowance per direction (spec §8).

Result shape¶

/// One discovered node (spec §5 result record).
pub struct TraversedNode {
    pub logical_id: Uuid,
    /// Hops from the nearest root (0 = root itself).
    pub depth: u8,
    /// Edge that first reached this node (`None` for roots).
    pub via_edge: Option<Uuid>,
    /// Confidence decay along the BFS discovery path (roots = 1.0).
    pub decay_score: Option<f64>,
}

/// One validated edge hop.
pub struct TraversedEdge {
    /// The edge version visible at the queried coordinate.
    pub version: EdgeVersion,
    /// Depth of the hop that used it (1-based).
    pub depth: u8,
}

/// Traversal counters (spec §5).
pub struct ExpandStats {
    pub rows_scanned: u64,
    pub edges_validated: u64,
    pub nodes_emitted: u32,
    /// Paths pruned by the decay floor, not budget-related.
    pub pruned_by_floor: u32,
}

/// Expansion result. `partial == true` iff any budget cap fired.
pub struct Expansion {
    /// Discovered nodes ordered by (depth, first-seen).
    pub nodes: Vec<TraversedNode>,
    /// Edges used, ordered by (depth, first-seen).
    pub edges: Vec<TraversedEdge>,
    pub partial: bool,
    /// Human-readable cap/visibility warnings.
    pub warnings: Vec<String>,
    pub stats: ExpandStats,
}

Expansion.stats distinguishes two kinds of "a node did not make it in": pruned_by_floor counts nodes cut by the confidence-decay floor, which is a scoring decision, while everything that trips partial is capacity, not scoring (see Budget and partial results).

Algorithms & invariants¶

BFS expansion, step by step¶

flowchart TD
    START([expand called]) --> VALDEPTH{depth in 1..=3?}
    VALDEPTH -- no --> ERR[Err: BadDepth]
    VALDEPTH -- yes --> ROOTS[For each root: get_as_of at vT,tT]
    ROOTS -- visible --> EMITROOT[Mark visited, emit at depth 0, decay = 1.0]
    ROOTS -- not visible --> WARNROOT[warning: root_not_visible]
    EMITROOT --> FRONTIER0[frontier = visible roots]
    FRONTIER0 --> HOPLOOP{d = 1..=spec.depth}
    HOPLOOP --> SORT[Sort frontier by node id byte order]
    SORT --> FORNODE[For each node in frontier, in order]
    FORNODE --> SCAN[Range-scan adjacency_out / adjacency_in\nprefixed by scope, node, optional type hash]
    SCAN --> ROWBUDGET{rows_scanned\n>= max_rows_scanned?}
    ROWBUDGET -- yes --> PARTIALROWS[partial = true\nwarning: budget_exhausted:rows_scanned\nstop entire expansion]
    ROWBUDGET -- no --> DECODE[Decode EdgeVersion from adjacency row]
    DECODE --> RESOLVED{Already resolved\nthis edge in this scan?}
    RESOLVED -- yes --> SCAN
    RESOLVED -- no --> EDGEVALID{"edge.valid_time.contains(vT)\nAND edge.tx_time.contains(tT)?"}
    EDGEVALID -- no --> SCAN
    EDGEVALID -- yes --> TOMB{edge.tombstone?}
    TOMB -- yes --> SCAN
    TOMB -- no --> DEDUPE{Edge id already\nin used_edges?}
    DEDUPE -- yes --> SCAN
    DEDUPE -- no --> VISITED{Neighbor already\nin visited set?}
    VISITED -- yes --> SCAN
    VISITED -- no --> DECAY[neighbor_decay = node_decay * weight_of edge_type]
    DECAY --> FLOOR{neighbor_decay < floor?}
    FLOOR -- yes --> PRUNE[pruned_by_floor += 1]
    PRUNE --> SCAN
    FLOOR -- no --> TARGETVALID{"get_as_of(neighbor, vT, tT)\nis Some?"}
    TARGETVALID -- no --> SCAN
    TARGETVALID -- yes --> NODEBUDGET{nodes_emitted\n>= max_total_nodes?}
    NODEBUDGET -- yes --> PARTIALNODES[partial = true\nwarning: budget_exhausted:total_nodes\nstop entire expansion]
    NODEBUDGET -- no --> EMIT[Mark visited, emit node + edge\nat this depth, push to next frontier]
    EMIT --> FANOUT{accepted_here\n>= max_fanout_per_node?}
    FANOUT -- yes --> PARTIALFANOUT[partial = true\nwarning: budget_exhausted:fanout:node\nstop this node's scan]
    FANOUT -- no --> SCAN
    PARTIALFANOUT --> FORNODE
    HOPLOOP -- frontier empty or depth exhausted --> DONE([Return Expansion])
    PARTIALROWS --> DONE
    PARTIALNODES --> DONE

Reading the algorithm as the code lays it out (Traversal::expand, core-engine/src/graph/traversal.rs):

1. Reject bad depth up front. spec.depth outside 1..=3 returns TraversalError::BadDepth before any storage access. The query layer should reject this at parse time too, but the engine refuses independently (spec §6 errors).
2. Seed the frontier from roots. Each root is checked with NodeReads::get_as_of(scope, root, valid_t, tx_t). A root not visible at the coordinate is skipped and recorded as root_not_visible:<id> in warnings, not treated as an error. Visible roots enter nodes at depth: 0 with decay_score: Some(1.0).
3. For each hop d in 1..=spec.depth: sort the frontier by node UUID byte order, then for each frontier node, range-scan its adjacency rows.
4. Per adjacency row: charge one unit against rows_scanned first (if the budget is already exhausted, stop the entire expansion, not just this node). Decode the EdgeVersion the adjacency entry points to, then run dual validation and the dedupe checks.
5. Attach decay and validate the target, described below.
6. Advance the frontier to the newly-visited neighbors and repeat, unless the frontier is empty (nothing left to expand) or the hop budget of spec.depth is exhausted.

Dual validation¶

The edge check happens first because it is a decode plus two interval containment tests against data already in hand; the node check is a second point lookup (effectively another get_as_of scan) and is only paid for edges that already passed validation, tombstone, dedupe, and the decay floor, in that order, so the expensive check runs last.

Visited-node and used-edge dedupe¶

There is a third, narrower, per-scan set: resolved_here, local to one (node, direction, type-range) scan, which collapses multiple stored versions of the same edge into the one version that resolves at the query coordinate before the edge-level checks run.

Budget and partial results¶

The three caps, exactly as implemented:

Only max_fanout_per_node is scoped to a single node; the other two caps are global and stop the whole BFS immediately, mid-hop, wherever it happens to be.

Deterministic ordering¶

Configuration¶

The spec (§8) states budget defaults are config, not semantics, and can be retuned from benchmark evidence (PR-029) without a spec amendment; the depth cap of 3 is semantics and would require one.

As-built notes¶

The spec's own Status is Draft, and §14's changelog has exactly one entry (the initial 2026-07-02 draft), so there is no recorded as-built deviation inside the traversal spec itself. Comparing the spec prose to core-engine/src/graph/traversal.rs directly surfaces one substantive difference not yet reflected in the spec text:

• Confidence decay is implemented inside expand, not left as a bare attach point. The traversal spec's Related line lists the confidence-decay spec as "scores attach here," describing a future integration. The code's module doc is explicit that this already happened: "Confidence decay (confidence-decay spec v0.2, F7-approved 2026-07-03): multiplicative per-hop decay with per-edge-type weights (default 0.7), roots at 1.0, BFS shortest-path-first as the max-path approximation (spec OQ-1 stance), and a floor ε below which paths are pruned rather than expanded." Concretely: Traversal owns a DecayParams (default_weight: 0.7, floor: 0.05, per-edge-type weights overrides), computed as neighbor_decay = node_decay * weight_of(edge_type) at the moment a hop is accepted, and any path whose decay falls below floor is pruned (counted in stats.pruned_by_floor) rather than attached or expanded further. This is PR-022's commit per the confidence-decay spec's own Implementation Approach (§10), which was gated on that spec's F7 math sign-off, completed 2026-07-03, one day after the traversal spec's draft date. The decay math itself, including the fusion with vector similarity, is the dedicated Confidence decay page's subject, not this one.
• The attach point for score fusion (multiplying decay against vector similarity into a single ranking score) is not in traversal.rs. Per the confidence-decay spec §5 and §10, fusion is PR-040's responsibility in query/fusion.rs, consuming decay_score off each TraversedNode as one of its two inputs. Traversal's job ends at producing decay_score; it does not know about vector similarity or the fusion exponent alpha.
• Everything else checked against the code matches the spec's proposed solution and architecture sections: depth bound {1,2,3}, per-hop fan-out and total-node caps, a global row-scan budget with partial-with-warning behavior, visited-set dedupe on logical id, and deterministic ordering by adjacency key bytes and (depth, first-seen).

Related¶

• Global temporal scan
• The version record model
• The tritemporal model
• Confidence decay
• Query language