Skip to content

Spec: Bounded Temporal Traversal Semantics

File: .ai/specs/core-engine/2026-07-02-traversal-semantics.md Status: Draft Owners: Storage lane Related: PR-018; composite-key-layout spec (adjacency layouts); tombstone-cascade spec (I1/I2); confidence-decay spec (scores attach here)

1. Overview

Defines hop semantics, bounds, temporal filtering, cycle handling, determinism, and the budget guard for graph traversal — the operator the query engine's expand stage and the PRD's "sub-millisecond 1–3 hop on 10M+ nodes" gate both depend on.

2. Problem Statement

Unbounded traversal is a denial-of-service primitive against ourselves: one high-degree node ("supernode") can turn a 3-hop query into millions of row reads. Undefined temporal filtering per hop produces time-travel paradoxes (traversing an edge that didn't exist at the query coordinate). Nondeterministic result order breaks pagination and makes the I2 byte-identical invariant untestable.

3. Proposed Solution

BFS with: depth ∈ {1,2,3} (hard cap 3 in v1); per-hop fan-out cap and total-nodes cap; a global row-scan budget that terminates with partial: true + warning rather than working unboundedly; per-hop bitemporal validation of every edge AND its target node against the query coordinate; visited-set on logicalId (shortest-path-first, so cycles terminate and each node's decay score reflects its nearest path); deterministic ordering (per-hop expansion ordered by adjacency key bytes; results ordered by (depth, first-seen index)).

4. Architecture

expand(scope, roots, spec{types?, direction, depth}, at=(vT,tT), budget)
  frontier = roots (depth 0)
  for d in 1..=depth:
    for node in frontier (key order):
      range-scan adjacency_{out|in} prefix [scope][node][typeHash?]
      per entry: charge budget; validate edge version at (vT,tT);
                 validate target node version at (vT,tT);   // no dangling hops
                 skip if visited; mark visited; attach decay score
    frontier = newly visited (capped)
  emit (nodes, edges, scores, partial?, stats)

5. Data Models

Adjacency keys per composite-key-layout spec (88B). Validation is a point lookup on edge_versions / node_versions using the covering key material. Result record: { logical_id, depth, via_edge, decay_score, path_first_edge }. Stats: rows scanned, edges validated, nodes emitted, budget consumed.

6. API Contracts

struct ExpandSpec { edge_types: Option<Vec<String>>, direction: Out|In|Both, depth: u8 /* 1..=3 */ }
struct Budget { max_fanout_per_node: u32 /* def 1_000 */, max_total_nodes: u32 /* def 10_000 */, max_rows_scanned: u64 /* def 250_000 */ }
fn expand(scope, roots, spec, at, budget) -> Result<Expansion>;  // Expansion.partial=true on any cap hit

Errors: depth>3 rejected at parse time (query-language spec); budget exhaustion is not an error — it is a partial result with warnings: ["budget_exhausted:<which>"].

7. UI/UX

Internal. telha debug expand <tenant> <node> --at <ts> renders a traversal with per-hop stats for supernode forensics.

8. Configuration

Budget defaults above, overridable per query within hard server ceilings (traversal.hard_max_* in config); Both-direction expansion counts each direction against the same budget.

9. Alternatives Considered

DFS (rejected: BFS gives shortest-path-first, which the decay model requires — a node's score must come from its nearest path). Depth > 3 in v1 (rejected: PRD scopes 1–3; deeper traversal wants a different algorithm class — revisit in Phase 4). Supernode denylists (rejected for v1: budgets already bound the damage; denylists add state and surprise). Erroring on budget exhaustion (rejected: partial-with-warning lets callers make progress and is honest about what was searched).

10. Implementation Approach

PR-018 commits: this spec → one-hop with dual validation → BFS executor with visited-set + caps → budget guard → temporal correctness tests (snapshot at T sees exactly the edges alive at T, both directions per I1/I2).

11. Migration Path

Greenfield; no stored state beyond what PR-017 writes. Budget defaults may be retuned from PR-029 benchmark evidence without spec amendment (they are config, not semantics).

12. Success Metrics

Temporal correctness suite green (creation-after-T and tombstone-before-T exclusion, historical inclusion). Determinism: identical inputs produce byte-identical Expansion across runs and platforms. Supernode test: 100k-degree node terminates within budget with partial=true. F6 gate: 1/2/3-hop p50 targets on the 10M dataset (PR-029).

13. Open Questions

  • OQ-1: Should Both direction dedupe an edge reachable both ways at the same depth, or report it twice with direction tags? Stance: dedupe on edge_logical_id, keep first by key order; confirm with query-language reviewers since it affects expand result shape.

14. Changelog

  • 2026-07-02 — v0.1: initial draft for peer review.