Skip to content

Created 2026-09-07. TTL: 90 days (expires 2026-12-06). Answers the Graph Versioning Prior Art Research Brief.

Graph versioning prior art: verdict and design mapping

The model exists, in four separate literatures, and none of them contradicts the shape we have. The two pointers per row are a transaction-time table with tuple timestamping (Snodgrass and Jensen), standardized as SQL:2011 system-versioned tables, built into Postgres as MVCC xmin/xmax, and first shipped as Stonebraker's 1987 POSTGRES Tmin/Tmax with a separate TIME relation, which is our actions table without the who and why. Datomic is the closest running system: transaction as a reified entity holding only metadata, effect recovered from the rows that point at it, retraction by a new datom, excision as the only true delete. Entities, links and claims map one to one onto Data Vault hubs, links and satellites, with entity_links as the Same-As Link; source record, canonical id and crosswalk are the settled MDM names for partial, entity and member link. Claims are FollowTheMoney statements (one row per observed value, raw value kept, provenance by construction) read with Wikidata's semantics (many values coexist, "best" is a projection, deprecated is retraction without deletion). The literature adds no different shape, but five gaps: a commit-ordered action sequence, a negative judgement so undo is stable, justifying claims on links, "wrong" versus "no longer holds", and the documented cost of the end-pointer UPDATE.

Confidence: high on the pattern identification; medium on how far the Data Vault and Datomic performance arguments transfer to an OLTP-sized Postgres graph.

Q1. The two-pointer row is system versioning with transaction stamps

H1 confirmed; the "pointer to a transaction row" variant has no separate name.

  • SQL:2011 is our write protocol: UPDATE end-stamps the old row and inserts the new one in one engine-atomic step, historical rows are immutable to applications, constraints are enforced on current rows only (Kulkarni and Michels, SIGMOD Record 2012).
  • POSTGRES 1987 stored Tmin/Tmax as transaction ids and a TIME relation mapping id to commit time because "the commit time of a transaction is not known in advance" (Stonebraker 1987). Postgres 6.2 removed user-visible time travel for "performance impact, storage size" (PG 6.3 docs).
  • Datomic: datom [e a v tx added], transaction entity holds :db/txInstant plus annotations, effect is the datoms tagged with the tx; re-asserting an existing fact is a no-op; excision "should never be used to correct erroneous data" (data model, tx reference, excision). Our shape is Datomic with the retracting tx denormalized onto the asserted row instead of a separate retraction datom.
  • Stamps must follow commit order. Jensen and Snodgrass show stamps must agree with serialization order or as-of queries return states no reader ever saw (VLDB 2001); MariaDB documents the start-time trap (system-versioned tables). uuid5 action ids carry no order and created_at is not commit order, so "graph as of action T" is undefined until actions gets a commit-ordered sequence.
  • Cost of the end pointer. Filling superseded_by_action_id is an UPDATE; if the column is in any index, partial IS NULL indexes included, the update is not HOT and every index gets a new entry (PG HOT). Data Vault 2.0 forbids updating the load end date and virtualizes it with LEAD() plus point-in-time tables (Scalefree, Insert Only); anchor modeling stores only interval starts (Rönnbäck et al., DKE 2010). Every modern insert-only school avoids the end marker; the two-pointer form trades one UPDATE per retirement for a cheap live predicate. Defensible at our scale, not the literature's default.
  • One time axis conflates correction with change. XTDB keeps system time exactly like ours and adds valid time so a query can choose "as best known" versus "without subsequent corrections" (Time in XTDB); Fowler: avoid bitemporal history when you can (Bitemporal History).
  • Undo as inverse transaction is the saga compensating transaction, which "semantically undoes" rather than restores (Garcia-Molina and Salem 1987); Korth, Levy and Silberschatz give soundness conditions once later transactions depend on the compensated one (VLDB 1990). Git's merge-revert trap is ours: re-running A's logic after undoing A must produce new rows, and undoing A must not revive rows a later B retired (revert a faulty merge).

Q2. Source record, canonical id, crosswalk: the registry-style MDM pattern

H2 confirmed. Every mature system stores a cross-reference table from source records to a canonical id with the entity derived; nothing found argues against a link table, one live member per partial, or undo by superseding.

  • Informatica MDM: base object plus XREF table, "each row in the cross-reference table represents a separate record from a source system"; linear vs tree unmerge (XREF). Medium confidence (pages partly blocked).
  • Senzing: each record in an entity carries MATCH_KEY and ERRULE_CODE, "the reason at the time this happened"; unmerge is re-resolution (entity spec).
  • Reltio: a crosswalk per source record; values remember their crosswalk so unmerge can return them; golden record is "a view, materialized on-the-fly"; the merge tree records time, mergeReason, mergeRules, user, losers; loser URIs keep resolving; manual merges are exempt from automatic unmerge (overview, merge tree).
  • nomenklatura and FollowTheMoney, the closest match: statements carry entity_id and canonical_id; the resolver stores edges (source, target, judgement, score, user, created_at, deleted_at), judgement POSITIVE, NEGATIVE, UNSURE; a decision mints a canonical id and links both ids to it (star, not chain); negatives block re-merging; removal is soft-delete then recompute; retired ids live in referents; "splits are always manual" (edge.py, resolver.py, identifiers).

Two gaps every commercial system fills and we do not: a per-link match justification (Senzing MATCH_KEY, Reltio mergeReason), and a negative judgement. Without the second, superseding a wrong merge is not stable: the next resolution pass re-merges it.

Q3. Claims are statements with provenance; read-time projection is the norm

H3 confirmed, with one refinement: superseding alone covers one of three retraction cases.

  • Wikidata: statement = main snak, qualifiers, references, rank, stable GUID; conflicting values coexist; rank is a read-time filter ("best rank" = preferred else normal); deprecated statements stay with references "to prevent users from re-adding disproven information" and require a reason (P2241); expiry is an end-time qualifier, not deprecation (DataModel, Help:Ranking, Help:Deprecation). Nanopublications draw the same line with distinct npx:retracts and npx:supersedes predicates (Kuhn et al. 2021). Wikidata relationships are statements with item values; qualifiers cannot carry references, which is the model's limit.
  • W3C PROV-DM: "Generation marks the beginning of an entity, whereas invalidation marks its end", at most one of each per entity-activity pair; changing a fixed aspect yields a new entity related by derivation; the qualified pattern turns a relation into an intermediate class so it carries attributes (PROV-DM, PROV-Constraints, PROV-O). This is the vocabulary for our two pointers.
  • FollowTheMoney relationships are Interval entities (Ownership, Directorship, Membership) with their own properties and proof; "assuming Thing entities are nodes and Interval entities are edges ... is false and will lead to nasty bugs" (Interval, entities).

Q4. Versioned stores: borrow Datomic's posture, do not build branches

  • Datomic has no persistent branches: one timeline, one arbiter (Waeselynck). As-of filters the current plus history indexes; the live db "pays no penalty for history"; high-churn attributes bloat history, hence :db/noHistory (filters).
  • TerminusDB, Dolt, Irmin, Fossil: content-addressed snapshots plus a commit DAG; branching is cheap, merge needs per-type three-way logic, TerminusDB reads traverse a layer stack that needs rollup (TerminusDB, Dolt storage). Their reasons to exist (merge, sync, decentralization) are not requirements here.
  • Event sourcing wins only for replay into new projections and retroactive recomputation, both costs we declined (Fowler, Young). Evidence that the action log should be the source of truth for our case: weak.

Recommendations for the data model (opinion, from the findings above)

  1. Add a commit-ordered seq to actions, assigned inside the committing transaction; define "as of" by it. Feeds part 4 and part 5. (Q1)
  2. Record justifying claim ids on the member link, plus the rule or score, as every MDM system does. Closes #21 the standard way. (Q2)
  3. Add a negative judgement record between two entities, or undo of a wrong merge is re-merged by the next pass. Feeds part 4's undo rule and the matching design. (Q2)
  4. Distinguish "superseded by a newer version" from "wrong, do not project" (Wikidata deprecated with mandatory reason, nanopub retracts vs supersedes) from "no longer holds" (a temporal qualifier on the claim). Superseding alone is one of three. Feeds part 3. (Q3)
  5. Keep relationships as interstitial records with their own claims, never bare edges. Feeds #18. (Q3)
  6. Say explicitly that source evidence dates are our valid time and there is no second axis; measure the non-HOT cost of filling the end pointer before indexing it; keep partial unique indexes on live rows only; keep a separate audited erasure path for legal deletion. (Q1, Q4)
  7. Adopt the vocabulary: source record, canonical id, crosswalk, match key, judgement, survivorship, split; wasGeneratedBy/wasInvalidatedBy for the two pointers. (Q2, Q3)

Undo rule to state: undoing action A must not revive rows a later action retired, and re-running A's logic after the undo must mint new rows (git revert-the-revert, Korth 1990). (Q1)