feat(ontology): add ontology graph and FK-aware reachability validation
What does this MR do and why?
The ontology stores nodes and edges as flat maps with no adjacency or reachability, so every consumer that asks "which kinds connect these two entities" or "which table backs this node" rescans those maps. This materializes that topology once and reuses it, and adds a pre-execution check that rejects a relationship whose declared type does not actually connect its two endpoints, telling the author which types do instead of returning a silently empty result.
Related Issues
Relates to #926 (closed), #1083
Testing
Ontology and compiler unit tests, plus ontology validation, all pass. Introspection output is byte-identical (parity tests), and the new validation check produces no false positives across the full compiler suite.
Performance Analysis
Replaces per-call linear rescans of the node/edge maps with materialized indexes; no query-result change and no regression risk.
- This merge request does not introduce any performance regression. If a performance regression is expected, explain why.
Agent context — long-form analysis, file-by-file walkthroughs, alternatives considered
First of three stacked MRs from the query-classifier plan; the partitioning foundation (!1962 (merged)) has merged, so this targets main directly.
crates/ontology/src/graph.rs (new). OntologyGraph::build(&Ontology) materializes:
- endpoint→relationship adjacency (
outgoing/incoming), sorted+deduped —neighbors,edges_between table_to_nodeindex (schema-version-prefix tolerant)anchor_fk(deduped by FK column) +fk_reachable(node → anchor entities its table FK-reaches) +anchor_nodes/global_nodes- per-triple
EdgeTemplate(scope,scope_preserving,destination_table,fk_column) and per-nodeNodeTemplate(sort_key,has_traversal_path,global,path_scopable,role_floor,redaction_id_column) denorm_coverage(entity, prop, dir) → {rel_kinds}reachable_within(start, max_hops)bounded BFS closure (absent from the flat ontology)
Pure, no DB. Exposed via Ontology::graph(); the existing cheap keyed accessors (is_scope_preserving_triple, edge_scope_for) stay as shims — edge_template is their materialized equivalent, so nothing regresses.
introspection.rs. node_relationships now reads OntologyGraph adjacency instead of the O(nodes × variants) rescan. Output format unchanged; the seven existing introspection tests pass as a parity gate.
passes/validate.rs. New check_reachability in the check_references chain (Traversal/Aggregation only). For each relationship whose both endpoints resolve to entities, it accepts when a declared type connects them via an edge triple or an FK-synthesized edge (fk_reaches), and otherwise errors naming the connecting types (or the reachable neighbor kinds). Wildcard * types are skipped.
FK-awareness is load-bearing: File -[IN_PROJECT]-> Project has no File → Project edge triple — it resolves through the project_id anchor FK. fk_reachable models exactly that path, so the check matches the compiler's real resolution semantics. Direction is deliberately ignored because the compiler flattens edge_source_kinds/edge_target_kinds across variants and matches regardless of the query's declared direction; a stricter check would false-positive on queries that run today.
There is no conservative fallback: an earlier draft skipped entities with zero adjacency to spare sparse unit-test fixtures, but the real ontology has zero isolated nodes, so the guard only ever hid fixture gaps. It was removed and the affected validate-pass fixtures now declare the edge variants their queries use.Making the compiler itself direction-aware and rejecting non-existent triples at resolution (not just as a hint) is a behavior change to query resolution and is deferred to a later MR in the stack.%{all_commits}