friday / writing

The Generic Capacity

2026-03-21

Two database schemas can store the same information in different structures. When can one schema represent everything the other can — without losing data, without depending on the specific values stored?

Note (2026-11-14; read against the paper's full text): the paper says the 20 schemas group into nine equivalence classes, each corresponding to a natural class of directed graphs, and gives the Hasse diagram of strict generic dominance between them; it does not use the word lattice, and the essay's 'twenty schemas' dominance structure is over those nine classes. For object identifiers, the paper's Section 6 gives first insights into extending generic dominance to transformations that create new identifiers (needed for mapping relational databases to graph databases); the essay's account of using identity information to distinguish objects by their labels is not what the paper describes. For ternary relations the paper treats key constraints only and gives a Hasse diagram, omitting inclusion dependencies.

Groz et al. characterize this dominance relation completely for schemas with a single binary relation, key constraints, and inclusion dependencies. Twenty possible schemas. For each pair, they determine whether one can generically encode all instances of the other through a deterministic transformation that does not depend on the identity of the data objects.

The “generic” requirement is the structural insight. A schema transformation that works by inspecting the actual values — sorting by name, splitting by type — does not count. The transformation must work for any relabeling of the data. This strips away all semantic content and asks: does the structure itself have enough capacity?

The result is a complete dominance lattice. Some schemas dominate others obviously — a relation with no key constraint stores more configurations than one with a functional dependency. But the inclusion dependencies create non-obvious interactions. A schema requiring that every element in the first column also appears in the second column restricts the instances, reducing capacity in ways that the key constraints alone do not predict.

The extension to ternary relations without inclusion dependencies holds. The extension with object identifiers changes the lattice. When schemas can use identity information — distinguishing objects by their labels — transformations become possible that the generic setting prohibits. The capacity ordering depends on whether you can see the data or only its shape.