Graphden documentation

Graph Constraints Reference

This document describes the integrity constraints enforced by the graphden storage layer. The slot/fn-slot/binding model handles most shape correctness through schema-level uniqueness (UNIQUE on the junction tables); the only protocol-level constraint that needs explicit code is dependency-cycle detection.

Entities

Protocol

(defprotocol GraphConstraints
  (validate-no-dependency-cycle! [this owner-fn-id ref-fn-id]))

Storage implementations enforce this by walking the fn → binding.ref-fn-id → binding-list-item.ref-fn-id graph.

Constraints

1. No Dependency Cycle

Rule: The dependency graph (any ref-fn-id, in either bindings or list-items) cannot form a cycle.

Rationale: Cycles cause infinite recursion at compile / execute time.

Example:

fn add-numbers
  binding {slot s-other, ref-fn-id multiply-numbers}

fn multiply-numbers
  binding {slot s-other, ref-fn-id add-numbers}    ✗ dependency-cycle

Self-reference at the per-binding layer: validate-no-dependency- cycle-impl carves out owner-fn-id == ref-fn-id — the bare self-ref write doesn’t throw at this check. HOWEVER the higher-level topological-sort (executor/composition/deps.clj) runs over the whole fn-def set at sync time and rejects any cycle, including bare self-refs. End result: graph-level recursion is structurally impossible today — neither self-ref nor mutual-ref nor any parent+ref combination passes both checks. See docs/ARCHITECTURE.md § Part 3 — Recursion and Cycles for the empirical demonstration, and RECURSION.md for the :fix-based recursion path (shipped) that adds recursion without a graph cycle.

Identity edges are not dependencies. A ref bound into a :fn-ref-typed slot (ids/identity-edge?) names its target without evaluating it — the compiled closure bakes the target’s id, nothing is called through the edge. So the cycle walk skips it at every layer (the per-binding constraint above, the sync-time topological-sort via slot-res/fn-ref-arg?, and compile-eager’s ref-DAG), and two services that each name the other (:service-endpoint :service …, SERVICES.md § Endpoints) are legal. The edge is still a real inbound reference for Used-by, GC and cross-org rejection.

The write-time guard (crud.validation/cycle-check-rej) applies the same rule to the edge being written: a ref-fn-id into a :fn-ref slot (or under a binding-level type-override to :fn-ref) runs no walk at all. On a binding or list-item update the guard keys the walk off the stored row’s owner fields (a PUT {ref-fn-id} alone carries neither fn-id nor binding-id), so re-pointing a ref is checked like creating one.

How the walk runs. generic-constraints/dependency-closure loads the ref’s execution graph through sp/resolve-execution-graph — the same recursive-CTE resolver the executor compiles from, O(1) round trips whatever the closure’s size — and walks it in memory over exactly the edges forward-deps-of follows, skipping identity edges; constraint- vector type NAMES ([:union :a :b], keywords the resolver does not chase) are resolved in one batched query per round. There is no visit cap on this path: binding a fn with a large closure (the editor’s own router) is a normal write. (The per-fn walker it replaced — four queries per visited fn, capped at 1000 visits → chain-too-deep — is gone.)

Error: :constraint-violation/dependency-cycle

2. Schema-level uniqueness

These hold by virtue of UNIQUE constraints in the schema, not the protocol:

Entity Unique key Note
fn (org-id, anonymous-hash) NULLS NOT DISTINCT anonymous fn dedup, per org — a tenant’s inline shape is its own row (records.ids/anonymous-fn-id mixes the org into the id); the platform’s package anons stay unique by hash
fn-slot (fn-id, slot-id) a slot is exposed at most once per fn
binding (fn-id, slot-id) one binding per (fn, slot)
ns (org-id, parent-id, name) NULLS NOT DISTINCT per org, like branch: two orgs may both hold packages/team; a root namespace (NULL parent) is unique too
branch (org-id, name) NULLS NOT DISTINCT per org

A UNIQUE key declared after an entity’s table exists is landed on a migrated DB by ensure-unique-indexes! on every migration pass (CREATE UNIQUE INDEX IF NOT EXISTS); existing rows that violate the new key leave a boot-time warning naming the index, never a broken boot — clean the duplicates and the next pass lands it. A retired key is dropped by name via *retired-indexes* in storage/postgres/migration.clj (an entry is added at retirement and removed once every deployment is past it).

Two former base-table UNIQUE keys were retired because their invariant is a property of the per-branch RESOLVED VIEW, not of the identity table (soft-deleted identity rows persist by design and would occupy the key forever; cross-branch divergence must not be blocked):

Entity Retired key Now enforced by
fn (namespace-id, name) check-fn-name-collisions! in VersionedStorage — live-view check on the writing branch AND on every branch forked off it, one batched read per write batch, advisory-lock-serialized (uniq/xact-lock!). Error: :constraint-violation/fn-name-collision
binding-list-item (binding-id, position) check-list-item-position-collision! in VersionedStorage — the writing branch’s own view only (see below). Error: :constraint-violation/position-collision

The same resolved-view rule covers resource-override.path (check-resource-override-path-collisions!, :constraint-violation/resource-override-path-collision).

Every check also runs where rows reach a view other than by a direct write:

List positions take the other side of that trade-off. Refusing main’s append because some feature branch already has an item at that position would leave main’s author no way out — they may not see that branch, and the editor computes the position for them. So an ancestor’s append is never refused on a descendant’s account; the descendant transiently shows two items at one position (ordered by id, so the compiled list is stable), and merging it back is refused with position-collision until its author moves one of them — the author who can fix it is the one asked to.

slot.name and slot.type-fn-id are NOT individually unique — two slots with the same name and type are distinct identities (sharing is opt-in via fn-slot pointing at the same slot-id).

Implementation

Storage Location
all backends generic-constraints/dependency-closure loads the execution graph through resolve-execution-graph (the PostgreSQL recursive-CTE resolver), then walks its indexed rows in memory. constraints/validate-no-dependency-cycle-impl uses that closure to reject a cycle.

The GraphConstraints extension is wired generically through graphden.storage.protocol.generic-constraints.

Testing

src/graphden/storage/protocol/contract_tests.clj exercises the protocol against any storage that registers GraphConstraints. The suite covers the per-binding contract (allow nil ref, allow self-ref, allow a distinct independent fn) plus concurrent CRUD. The sync-time topological-sort rejection of graph cycles is a separate layer.

bb test  # runs unit tests

Inheritance regression e2e tests live in tools/browser-test/edit-inheritance-regression.test.js: