Canonical IDs, and Why Your Graph Forks Without Them

Every knowledge graph that forked did so for one of two reasons: the same real thing arrived under two identifiers and nothing reconciled them, or an identifier that used to mean one thing quietly started meaning another. Both are prevented by the same design, and it is mostly a table.

Four rules, and what each one prevents

The third rule is the one people push back on, because a natural key feels free. The counterexample takes about four minutes to find in any real system: two companies share a VAT number after a restructuring; a person changes their email; a supplier code is recycled by the ERP three years after the supplier was deleted. Each of those silently merges or splits entities that nobody decided to merge or split.

What the identifier itself should be

A prefixed ULID or UUIDv7 is a good default. Both are 128-bit, both sort roughly by creation time, and the sortable property matters more than it sounds — random UUIDv4 primary keys scatter writes across a B-tree index and hurt insert performance on large tables, while time-ordered ids append.

co_01J9XQ4T2M8VZK3B7NR5PW0FDS   company
pe_01J9XQ4T2M8VZK3B7NR5PW0FDT   person
pr_01J9XQ4T2M8VZK3B7NR5PW0FDV   product

The two-letter prefix is not decoration. It makes an id self-describing in a log, makes a mis-typed foreign key visible on sight, and makes it impossible to pass a company id where a person id was expected without somebody noticing. It does not violate the opacity rule, because the type of an entity is the one thing that genuinely does not change — and on the rare occasion it does, that is a split, which is handled below.

Avoid auto-increment integers for anything that crosses a system boundary. They leak volume, they collide when two environments merge, and they invite the assumption that ids are comparable.

The alias table is the real design

The canonical id is boring. The interesting part is the table that maps everything else onto it:

CREATE TABLE entity (
  id          text PRIMARY KEY,          -- co_01J9...
  type        text NOT NULL,
  status      text NOT NULL              -- active | merged | tombstoned
                CHECK (status IN ('active','merged','tombstoned')),
  merged_into text REFERENCES entity(id),-- set iff status = 'merged'
  created_at  timestamptz NOT NULL DEFAULT now(),
  CHECK ((status = 'merged') = (merged_into IS NOT NULL))
);

CREATE TABLE entity_alias (
  source      text NOT NULL,             -- 'sap', 'salesforce', 'vat', 'wikidata'
  source_key  text NOT NULL,             -- the id in that system
  entity_id   text NOT NULL REFERENCES entity(id),
  confidence  numeric(4,3) NOT NULL DEFAULT 1.0,
  asserted_by text NOT NULL,             -- 'loader:sap', 'steward:jkarl', 'er:v3'
  asserted_at timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (source, source_key)
);

CREATE INDEX ON entity_alias (entity_id);

The primary key on (source, source_key) is the load-bearing constraint: one external record maps to exactly one canonical entity, and re-running an import cannot create a second mapping. That is what makes ingestion idempotent, which is the property keeping a knowledge graph fresh is built on.

asserted_by earns its column the first time somebody asks why a record is attached to the wrong company. A mapping written by a steward should not be silently overwritten by the next automated run, and without this column you cannot tell which is which.

Merging without breaking references

The wrong way is to pick a survivor, repoint everything, and delete the loser. It seems clean and it destroys information: the deleted id exists in exports, log lines, other companies’ systems and a hundred caches, and every one of those now dereferences to nothing.

1. Choose a survivor deterministically. Oldest created_at is a fine rule and its only real virtue is that it gives the same answer every time, which matters when two workers process the same merge concurrently.
2. Mark the other as merged — set status = 'merged' and merged_into = survivor. Do not delete the row. Ever.
3. Repoint the aliases so that every external key that pointed at the loser now points at the survivor.
4. Record the merge as an event with the pairwise evidence and the score that caused it, so that an un-merge has something to work from and an auditor has something to read.
5. Leave the facts where they are and resolve at query time, or migrate them in a background job. Do not do both.

BEGIN;

UPDATE entity
   SET status = 'merged', merged_into = $survivor
 WHERE id = $loser AND status = 'active';

UPDATE entity_alias
   SET entity_id = $survivor
 WHERE entity_id = $loser;

INSERT INTO entity_merge_event (survivor, absorbed, score, evidence, decided_by)
VALUES ($survivor, $loser, $score, $evidence::jsonb, $actor);

COMMIT;

The rule that makes this safe is that merged_into may only ever point at an active entity. Enforce it — either in the merge transaction or with a trigger — because a chain of merges pointing at merged entities is how you get the cycle the resolution query below has to defend against.

Splitting, which is the hard one

A split happens when a merge was wrong, or when a real thing divides — a company demerges into two. Both are the same operation and both break the naive instinct, which is to keep the original id for “the main one” and mint a new id for the other.

That instinct violates immutability in the way that matters. Any reference to the old id created before the split meant “the combined thing”. If the old id now denotes only one half, every historical reference has silently changed meaning, and there is no record anywhere that it did. A report re-run over last year’s data quietly returns different numbers.

1. Mint new ids for every resulting entity. All of them, including the one that feels like the original.
2. Tombstone the old id — status = 'tombstoned' — and record the split event listing the new ids.
3. Resolve the old id to an ambiguity, not to a successor. A lookup returns HTTP 300-style “this identifier now corresponds to several entities” with the list. That is an honest answer and callers can handle it; a wrong single answer cannot be handled at all.
4. Reassign the aliases explicitly. Every external key that pointed at the old entity has to be decided, one at a time, because that decision is exactly the information the split is made of. Aliases nobody can assign stay unassigned and appear in a stewardship queue.
5. Do not migrate historical facts. A fact asserted about the combined entity in 2024 was true of the combined entity. Leave it attached to the tombstoned id, where it remains findable and correctly dated.

Splits are rare and expensive, which is precisely why the merge threshold in entity resolution should be set for precision. Every automatic merge is a bet that you will not have to do this.

The resolution query

Every read path goes through one function: given any id anybody has ever held, return the current entity. Following merged_into is a recursive walk, and it needs cycle protection because the invariant above will eventually be violated by a bug.

WITH RECURSIVE resolved AS (
  SELECT id, merged_into, status,
         ARRAY[id] AS path,
         0 AS depth
  FROM entity
  WHERE id = $1

  UNION ALL

  SELECT e.id, e.merged_into, e.status,
         r.path || e.id,
         r.depth + 1
  FROM entity e
  JOIN resolved r ON e.id = r.merged_into
  WHERE NOT e.id = ANY(r.path)     -- cycle guard
    AND r.depth < 16               -- depth guard
)
SELECT id, status
FROM resolved
ORDER BY depth DESC
LIMIT 1;

The path array is the portable cycle guard and works on any engine with recursive CTEs. PostgreSQL 14 and later also offer a CYCLE clause that does the same thing declaratively; the array version is written here because it runs everywhere and makes the mechanism visible.

The same walk in Cypher, if the graph is the system of record:

MATCH (start:Entity {id: $id})
OPTIONAL MATCH path = (start)-[:MERGED_INTO*0..16]->(current:Entity)
WHERE NOT (current)-[:MERGED_INTO]->()
RETURN current.id AS canonical_id, current.status AS status
LIMIT 1

Cache the result aggressively and invalidate on merge events. The resolution lookup sits in front of every query in the system, so it is the one place where a few milliseconds is worth engineering away — and it is also the one place where a stale cache means serving the wrong entity, so the invalidation has to be event-driven rather than time-based.

External identifiers

Wikidata QIDs, GLEIF LEIs, ISINs, GTINs, ORCIDs and company register numbers are all attributes, stored in entity_alias like any other source. Two disciplines make them useful rather than dangerous:

• Record who asserted the link and when. A QID matched by a string-similarity job is not the same evidence as one confirmed by a person, and only the asserted_by column can tell them apart later.
• Never treat an external identifier as your primary key. External registries merge and split their own entities on their own schedule, and a Wikidata item can be merged into another by a volunteer editor on a Tuesday. When that happens you want to update one row in an alias table, not migrate a primary key.