Skip to main content

Validation graph — implementation architecture

This is the runtime companion to the validation graph design walkthrough. The walkthrough explains what was decided (D1–D26); this page explains how the merged code works — the data model in practice, the engine's query paths, and the worked examples and patterns that recur across the module.

Everything here lives under backend/validationgraph/ (package ai.aucert.validationgraph), builds with Bazel, and stores in Postgres 18 + pgvector. Open-core boundary and package map: backend/validationgraph/README.md.

The hybrid model: an append-only log with a materialized projection​

The single most important idea is D3, the hybrid (a′) model. Two representations of the same truth:

  • The claims table is the source of truth — strictly append-only. Corrections, status changes, retractions (D10), and splits/merges (D18) are never updates or deletes; they are new claim rows. This is invariant C1.
  • The entities / edges rows carry a materialized projection — validation_status, confidence, and properties columns that cache "what is true right now, for the default context." This is the (a′) hot read path, so an ordinary read does not replay the log.

This is event sourcing with a CQRS read model, applied at row granularity: the claims log is the event stream, the materialized columns are the projection. The payoff is everything downstream depends on — per-tenant migration by replay (D26), and "restoration = retract-the-retraction" (D10) — and it falls straight out of never mutating history. The cost is that the projection must be re-derived on every write, which is the entire job of CurrentTruthMaterializer.

A worked example: a login screen​

Modeling a login screen and its "forgot password" link uses both axes of the model:

  • Nodes (entities rows): a Screen entity (screen_login), a Component entity for the button (btn_forgot_password), and the destination Screen (screen_forgot_password).
  • Edges (edges rows): a contains edge from screen_login to btn_forgot_password, and a navigates_to edge from btn_forgot_password to screen_forgot_password.
  • Claims (claims rows): every one of those nodes and edges exists because a claim asserted it. The rover crawling the app emits "claim: screen_login is a Screen", "claim: btn_forgot_password navigates_to screen_forgot_password", etc. The materialized entities/edges rows are the current-truth projection of those claims.

To trace "how does a user get from login to password reset?", you do a graph traversal over the navigates_to edges (see traversal below) — the path falls out of the edge topology.

The claim lifecycle and chain-aware liveness​

CurrentTruthMaterializer answers one question on every write: what is current truth? The answer is the latest live, non-retraction claim about the target, by asserted_at (with a deterministic claim_id tiebreak). The subtlety is the word live, because a retraction is itself a claim and can itself be retracted (restoration, D10):

A claim is dead iff an odd number of its live retractions target it.

So liveness is resolved over the whole retraction chain to a fixed point: start optimistic (all retractions live), repeatedly drop any retraction that is itself dead, until the live set stops shrinking. The consequences:

  • One retraction kills a claim.
  • Retract-the-retraction restores it (even parity → live again).
  • Multi-party retraction is preserved rather than collapsed.

Worked example — claim c1 asserts node A; r1 retracts c1; r2 retracts r1:

StateLive retractions targeting c1Parityc1
c1 only0evenlive
+ r11 (r1)odddead
+ r2 (retracts r1)0 (r1 now dead)evenlive again

The same parity rule is what makes the mutual-retraction paradox (r1 retracts r2, r2 retracts r1) resolve deterministically to both dead rather than looping.

Implementation note. The liveness rule currently exists in two places — core/claims/CurrentTruthMaterializer (write path) and core/time/RetractionLiveness (bitemporal read path) — a deliberate decoupling so the read path does not import the write path. It is subtle enough that the two copies are a divergence risk worth consolidating into one shared primitive later.

Topology on first claim​

A claim about a not-yet-seeded node/edge used to be a no-op (the claim was logged, but nothing materialized). As of the topology fix, TopologyWriter creates the topology row on the first claim about an entity, then materializes. This matches discovery-driven ingestion: the rover often learns about a node via the first claim about it — there is no separate "create entity" step. Asserting Screen X exists brings X into being rather than dropping silently into the log.

The storage engine and its five paths​

PostgresGraphStorageEngine (the day-1 GraphStorageEngine, D26) is a thin transaction + scope orchestrator. Every operation runs through the same TenantGuc.withTenant envelope, and the real work is delegated to focused collaborators:

PathMethodsMechanism
WriteinsertClaim, retractClaimappend-only INSERT + re-materialize, in one transaction
ReadgetNode, getEdge, outgoingEdges, incomingEdges, querycurrent-truth reads + CEL filter pushdown
Traversaltraverse, findShortestPathrecursive CTEs + bidirectional BFS
Bitemporal(core/time) trueNow, trueAt, believedAttwo time axes over the claim log
Conditions(core/conditions) ConditionEvaluatorCEL + registry-backed variable resolution

Reads and CEL filter pushdown​

query compiles the caller's CEL filter into a SQL WHERE clause so Postgres does the filtering, not Kotlin. The win is obvious: you do not pull 10,000 rows into app memory to keep 12. The catch is that not every CEL expression maps to SQL, so there is a pushable subset with an in-memory fallback for the rest — the full CEL filter remains the authoritative gate.

Traversal: bounded BFS + bidirectional shortest path​

traverse is a bounded breadth-first walk via a Postgres WITH RECURSIVE CTE. findShortestPath uses bidirectional BFS: expand from both endpoints and stop when the frontiers meet, turning roughly b^d explored nodes into b^(d/2) + b^(d/2) (for branching factor b, depth d). At b=30, d=6 that is ~1,500 nodes instead of ~700 million. Running it inside a recursive CTE keeps the whole walk in Postgres — no per-hop round trips.

Bitemporal-lite: two time axes​

Each claim carries two independent time axes (D17):

  • Observation time (asserted_at) — when we recorded the claim (system time).
  • Validity time (valid_from / valid_to, half-open [from, to)) — the real-world interval the fact actually held.

Three query modes fall out of pinning different axes:

MethodQuestionAxis pinned
trueNow"What is true right now?"validity = now
trueAt(T)"What was/will be true at validity-time T?"validity = T
believedAt(T)"What did we believe at observation-time T?"observation ≤ T

The crux is in believedAt: it resolves liveness using only the retractions asserted at-or-before T — a retraction issued after T must not retroactively rewrite what we believed back then. trueNow/trueAt use the full retraction set. That single difference — bounding the retraction set by observation time — is what makes this genuinely bitemporal rather than just validity-time filtering. And trueNow with no validity windows set collapses exactly to the materializer's current-truth answer, so the read and write paths agree by construction.

The two three-layer registries​

Types and variables share the same 3-layer shape (D12.3 / Q8.1): L1 BUILTIN, L2 ECOSYSTEM, L3 TENANT. Resolution walks them most-specific-first (L3 → L2 → L1).

Variable registry (core/variables)Type registry (core/types)
Storageentities rows in _variables partitionentities rows in _types partition
L1/L2 homeunder the _system tenantunder the _system tenant
L3 homethe tenant's own partitionthe tenant's own partition
Naming ruleL1/L2 reserved; L3 must be tenant-prefixedidentical

The most important subtlety: L1 means different things for the two registries. For variables, L1 (BUILTIN) is the primitive type vocabulary (VariableType: boolean, version, enum, …) — it has no rows in the partition, and resolve() therefore never reads it; it is consulted at type-check time, not resolve time. For types, L1 is the seeded built-in content/domain types (Screen, Component, Workflow, Bug, … in R__seed_builtin_types.sql) — which do have rows.

The type system adds, beyond the variable registry: single inheritance (extends), capability interfaces (implements — Searchable, Embedded, …), and a required-core vs open-extension property contract (declared required-core properties are validated at write; everything else is carried unvalidated). That is "closed schema where it matters, open schema everywhere else" — the graph stays schemaless enough for messy discovery data while the few properties the pipeline depends on are guaranteed present.

Monotonicity hints​

Variables carry a monotonicity hint (D11): none, strict-incremental, mostly-incremental, temporal, partial-order. The day-0 seed gives app_version the canonical mostly_incremental hint — it generally increases but tolerates occasional non-monotonic observations (downgrades, enterprise rollbacks). strict-incremental would reject any observed downgrade as a violation; mostly-incremental was chosen because real-world downgrades happen. This hint is what the inference engine consumes.

Conditions, inference, and ACL​

Condition evaluation​

ConditionEvaluator (core/conditions, VG-15) is a thin composition layer: it joins the CelEvaluator (VG-07, Kleene three-valued CEL) with a RegistryVariableResolver that backs CEL's pluggable VariableResolver seam with the per-tenant variable registry. Two guarantees:

  • Full context → deterministic True / False, never Unknown.
  • Missing binding → Kleene Unknown, never false. A validation substrate must distinguish "don't know" from "false"; collapsing unknown → false silently corrupts every downstream decision, so this layer returns Unknown and forces the caller to choose a disposition.

Custom CEL functions​

CEL ships with only generic operators, so the evaluator (VG-07) registers domain custom functions in a CustomFunctionRegistry, each co-locating its declaration (the type signature CEL compiles against) with its binding (the Kotlin that runs it). Two are wired today:

  • has_tag(id, "tag-x") → real tag-membership lookup (the TagAwareStorageEngine decorator, tags).
  • version_in_range(v, lo, hi) → a worked example of why a custom function is needed at all. A plain >= comparison on app_version would compare versions as strings — and lexically "3.10" < "3.9", which is wrong. version_in_range instead dispatches to the variable's declared version comparator (semver / date / internal scheme, per its VariableType.VERSION definition), so version_in_range(app_version, "3.0", "4.0") returns the correct answer for app_version = 3.10. The comparator lives with the variable definition, not the CEL expression, so the same condition text behaves correctly for every versioned variable.

This is the seam the enterprise ABAC layer (P12) extends: a tenant's custom CEL policy functions register here without touching the evaluator core.

Inference engine​

The InferenceEngine (core/inference, VG-16) is where the monotonicity hint earns its keep: it infers facts never directly observed by exploiting the value order. If app_version is monotonic and you observed ≥ 3.5 yesterday, you can infer ≥ 3.5 today without a fresh observation. Every inferred answer carries a DerivationChain — its reasoning trail — so the system can explain "I concluded X because observation Y + monotonicity rule Z." That explainability is the difference between a validation substrate (must justify) and a guesser. Contradiction semantics flag an observation that violates the declared monotonicity rather than silently producing nonsense.

Built-in role-derived ACL​

The open-core ACL (core/acl/core, VG-17, D7/D13 layer 1) derives permissions from ownership, not from stored policies. Four roles — Creator (read-only; records authorship), Owner (full), Maintainer (read+write), Viewer (read-only, explicit-assignment only) — each map to an explicit set of namespaced Actions.

The performance trick is denormalization: each entity/edge already carries its Ownership fields, so "can principal X write entity Y?" needs only Y's ownership — no _acl partition read, no join. That is what makes deny-by-default workable: a brand-new entity is instantly usable by its creator/owner with no policy authored. Note there is no entity:delete verb — the append-only model makes "delete" either a soft-delete (entity:write) or a retraction (claim:retract). Custom roles, CEL object_filter policies, and property-level ACL are the enterprise ABAC layer (P12) — deliberately not in core.

The replica index (core/vector/pgvector, VG-19)​

PgvectorVectorIndex realizes the D20 replica-index model: vectors live on entities.embedding as source of truth, and this adapter maintains a separate copy in vector_index_entries, keyed by (tenant_id, entity_id, embedding_model_id). Why a separate table? entities.embedding is a dimensionless vector column on purpose (D21 — dimension is a property of the model, so multiple models coexist), but pgvector HNSW needs a fixed dimension at index-creation time. So HNSW creation is deferred: ensureHnswIndex is a no-op today, v1 search runs a sequential scan with the <=> cosine operator (correct within the year-1 <50M-embedding envelope), and real HNSW indexes are added by Flyway migration once a model's dimension stabilizes.

Open item (VG-VEC-MIG). vector_index_entries is currently created at runtime by ensureSchema, not by a migration, so it has no RLS today — isolation rests solely on the WHERE tenant_id = ? clause. The adapter's setTenantGuc uses SET LOCAL, which is a no-op in the autocommit connections search uses, and would go fail-closed (empty results) the moment RLS is added. The tracked fix moves the table into a Flyway migration and adds RLS; the GUC binding must move to the parameterized set_config(..., is_local := true) form inside the query's own transaction at the same time.

The search orchestrator (core/vector/search, VG-22)​

SearchSemanticService composes on top of the adapter: three input modes (RawVector, ByEntity, ByNaturalLanguage via a TextEmbedder), a CEL structural filter, and ACL redaction (results the principal cannot see are dropped — even when one is the nearest vector). A DeterministicHashEmbedder hashes text to a fixed vector so search is reproducible in CI without a real embedding service.

Cross-cutting patterns​

Tenant isolation: fail-closed RLS​

Every tenant-scoped table has FORCE ROW LEVEL SECURITY keyed on the app.current_tenant_id GUC (migration V002, D15.1). The policy is fail-closed: when the GUC is unset, current_setting(..., true) is NULL, the predicate tenant_id = NULL is never true, and the connection sees zero rows. TenantGuc.withTenant binds the GUC for one transaction via the parameterized set_config('app.current_tenant_id', ?, true) — bound as a value, never string-concatenated, and transaction-scoped so it never leaks onto the next pooled-connection borrower. The cross-tenant fuzz test (VG-18) proves this holds under randomized op interleavings, and crucially runs as a non-superuser role — a superuser bypasses RLS entirely, so a test run as superuser would pass even with RLS fully broken.

Tags as a decorator (core/storage/tags, VG-21)​

TagAwareStorageEngine is a decorator around the Postgres engine. Its one job: make the has_tag(id, "x") CEL function — shipped as an empty-set mock in VG-07 — resolve real tag membership from entity_tags / edge_tags. All other ops pass straight through. DI binds it two ways: as TagAwareStorageEngine concretely (for tag-management code) and as GraphStorageEngine (for everyone else) — same instance, two views — so every consumer transparently gains has_tag support with zero code change. Tags are cross-partition (D14): a tag can mark entities in any partition.

Audit log vs claim log​

ClaimAuditWriter records an audit_log row on every claim write (VG-23). This is a second log, distinct from the append-only claim log: the claim log records what facts changed (domain truth, for replay/materialization), while the audit log records who did what, when (operational accountability — principal, action, timestamp, for compliance and forensics).

Change feed (core/eventbus, VG-20)​

PostgresEventBus is a Postgres LISTEN/NOTIFY adapter behind the EventBus interface. It is at-most-once and ephemeral — a "doorbell, not the mail." Durable delivery is the claim log's job (D3/C1); a subscriber that misses a notification recovers by reading forward from a cursor over the durable log. A LISTEN identifier must be quoted to match a mixed-case pg_notify channel, and the notify must be committed to fire.

Interface + adapter, and bind to the interface​

All five locked plug-in abstractions (GraphStorageEngine, VectorIndex, EntitlementSource, IdentityServiceClient, EventBus, §10) have their interface in core/ and their day-1 implementation in core/ too. Koin keys bindings by declared type, so a binding must name the interface: single<EventBus> { PostgresEventBus(...) }, not single { PostgresEventBus(...) }. Binding the concrete type forces consumers to get<ConcreteAdapter>(), coupling them to the adapter and defeating the in-memory swap the interface exists for. (This was a real, latent bug in the type-registry binding, fixed while still a one-token change.)

Proto → gRPC codegen​

proto/validation-graph.proto (package aucert.validationgraph) is the API contract; proto/BUILD.bazel compiles it to Kotlin stubs via the proto_library → kt_jvm_proto_library → kt_jvm_grpc_library chain. Generated code is never committed — protoc is hermetic, so the Kotlin lives only in bazel-bin and is regenerated every build. (Contrast JOOQ, which does commit its generated sources because it needs a live database to generate against.) MODULE.bazel must declare exactly one protobuf bazel_dep — a duplicate repo name is a hard module-resolution error, which is why "union both sides" is the wrong default for MODULE.bazel.

Migration by replay​

Because the claim log is immutable and current truth is derived, a tenant can be migrated — to a new schema, region, or clean database — by replaying its log rather than copying mutable state (D26). The S7 regression test (MigrationReplayRegressionTest) is the guardrail: it replays the log onto a fresh Postgres and asserts the rebuilt current truth matches, catching any change that makes materialization non-deterministic.

Implementation status​

AreaStatus
Domain model, claims, write/read/traversal/bitemporalshipped
Registries (types + variables), seeds, conditions, inferenceshipped
ACL (role-derived), tags, audit, EventBus, vector + searchshipped
Tenant isolation (RLS + GUC + cross-tenant fuzz)shipped
proto → gRPC Bazel codegen toolchainshipped
Scenario regression suite S1–S7shipped
gRPC service methods (ValidationGraphService)skeleton — still return UNIMPLEMENTED; the engine exists but is not yet wired to the RPC surface
vector_index_entries → Flyway migration + RLS (VG-VEC-MIG)deferred
Persist principal_type (D8 gap, VG-PTYPE)deferred
Enterprise ABAC layer (custom roles, CEL policies, property ACL)out of open-core scope (P12)