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?
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.