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.

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_node index (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-node NodeTemplate (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}

Edited by Michael Usachenko

Merge request reports

Loading
Loading