Object-Graph Identity Table¶
Reference-resolution structure — instantiates Round-Trip Serialization Contract
A side table that assigns each object a stable id the first time it is seen, so shared nodes and cycles serialize once as references and rebuild as the same object — not as duplicated trees.
A native object graph is held together by memory pointers, and pointers do not travel. When two fields point at the same object, or when objects point back at each other in a cycle, a naive serializer either duplicates the shared node into two independent copies or spins forever chasing the loop. Object-Graph Identity Table solves this by keeping a running table that maps each object to a portable id the first time it is encountered; every later reference to that object is written as "see id N" instead of a fresh copy. Its defining move is preserving identity, not just value: after a round trip, two references that pointed at one object must again point at one object, and a cycle must come back as a cycle — the graph's sharing topology is the thing being conserved. It draws the boundary of what counts as one object, hands out the ids, and drives the two-pass rebuild that resolves them.
Example¶
A 3-D game engine needs to save a level to disk. The level is a scene graph: mesh nodes, materials, and lights, where dozens of surfaces reference the same "brushed metal" material object, and a rigging skeleton contains parent/child bones that point back at each other. Serialized naively, the one shared material would be written out dozens of times — bloating the file and, worse, reconstructing as dozens of distinct materials, so editing one no longer changes the rest — and the bone cycle would loop forever.
The engine's serializer keeps an identity table, in the style of Python's pickle memo[n1]. As it walks the graph, the first time it meets the brushed-metal material it assigns id 42 and writes the full object; every subsequent surface just writes a reference to 42. The bone cycle is written as bones plus reference-links, never recursively inlined. On load, the deserializer makes a first pass to create empty stubs keyed by id, then a second pass to wire references to those stubs — so shared nodes reunite at one object and the cycle closes. Edit the reloaded material once, and every surface updates, exactly as before the save.
How it works¶
- Bound the object. Decide what constitutes one identity-bearing object (and what is inlined value), so the table keys are well defined.
- Assign on first sight. Maintain a map from object to id; on first encounter, allocate an id and serialize the body; on any later encounter, emit only the id reference.
- Break cycles by reference. Because repeats become references, a cycle is written as a finite set of nodes plus links rather than an infinite inlining.
- Reconstruct in two passes. Create all objects as id-keyed stubs first, then resolve every reference to the already-created object — restoring shared identity and closing cycles.
Tuning parameters¶
- Identity criterion — reference identity versus value identity (two equal-but-distinct objects: merge or keep separate?). Merging shrinks the payload but can wrongly unify things the domain treats as different.
- Id scheme — sequential integers (compact, position-dependent) versus content or UUID keys (stable across payloads, larger). The choice trades size against cross-payload referenceability.
- Traversal order — depth-first versus breadth-first assignment. Order changes which node "owns" the full body, affecting diff stability.
- Inlining threshold — small leaf objects inlined by value versus always tabled. Inlining trims table overhead but forfeits shared-identity guarantees for those objects.
When it helps, and when it misleads¶
Its strength is defeating reference collapse — the round-trip illusion where a graph "serializes fine" but comes back as duplicated trees with the sharing silently gone. Anywhere identity and shared substructure carry meaning (scene graphs, ORMs, document models, dependency graphs), this table is what makes the reconstruction faithful rather than merely value-equal.
Its failure mode is subtle: an over-eager identity criterion can merge objects that were meant to be distinct, or a mismatched criterion across producer and consumer can quietly change the graph's shape. It also adds bookkeeping and a two-pass load, and a stale or non-deterministic id scheme undermines diffs and caching. The classic misuse is assuming value equality implies identity preservation — a serializer can round-trip every field yet destroy sharing. The guarding discipline is to test explicitly for shared-node and cycle survival, not just field equality, using a graph-aware equivalence check.
How it implements the components¶
source_structure_boundary— it decides what counts as one identity-bearing object versus inlined value, drawing the graph's serialization boundary at the node level.identity_and_reference_map— the table is this component: portable ids standing in for native pointers, with shared references and cycles expressed as id links.deserialization_reconstruction_rule— its two-pass stub-then-resolve procedure is a reconstruction rule specialized to restore identity and close cycles.
It defines no field-level types or validation — that is a schema codec such as JSON Schema Encoder/Decoder's serialization_schema_contract — and it holds no version_and_migration_policy; evolving the graph's shape across versions is Versioned Decoder Adapter's job, not this table's.
Related¶
- Instantiates: Round-Trip Serialization Contract — supplies the identity-and-reference face of the contract for graphs with sharing and cycles.
- Sibling mechanisms: Archive Manifest · Avro Schema Registry · Canonical JSON Normalization · JSON Schema Encoder/Decoder · Payload Signature or Hash · Protocol Buffers Message Definition · Round-Trip Fixture Test · Versioned Decoder Adapter · XML Schema and Parser
Editorial Notes¶
Form Classification¶
Form family: Structure, Architecture & Configuration
Rationale: Object-Graph Identity Table operates as a configured physical, technical, or logical arrangement whose structure creates the effect because it a side table that assigns each object a stable id the first time it is seen, so shared nodes and cycles serialize once as references and rebuild as the same object — not as duplicated trees.
Independent corroboration: The frozen evidence defines Object-Graph Identity Table as 'A side table that assigns each object a stable id the first time it is seen, so shared nodes and cycles serialize once as references and rebuild as the same object — not as duplicated trees', so its operative form is Structure, Architecture & Configuration.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Object serialization systems developed memo or handle tables so shared references and cycles are written once and reconstructed with identity intact.
Review resolution: Both independent reviews agree on primary origin computer_science; reconciliation resolves encyclopedia_synthesis_disagreement. Formative alternate lineages retained: none. The broader reach of later applications is kept separate as domain_reach=specialized; origin_mode=single_lineage describes the historical relationship among lineages. Confidence is conservatively reconciled to high, and encyclopedia_synthesis=true preserves the reviewers' boundary judgment.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Python's pickle module maintains a memo table mapping already-serialized objects to references, so shared and cyclic object structures are written once and reconstructed with their sharing intact rather than duplicated; Java's object serialization uses an analogous handle table. ↩