On the generic information capacity of relational schemas with a single binary relation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917351594655744 |
|---|---|
| author | Groz, Benoît Hidders, Jan Pardal, Nina Bussche, Jan Van den Wieczorek, Piotr |
| author_facet | Groz, Benoît Hidders, Jan Pardal, Nina Bussche, Jan Van den Wieczorek, Piotr |
| contents | We consider database schemas consisting of a single binary relation, with key constraints and inclusion dependencies. Over this space of 20 schemas, we completely characterize when one schema is generically dominated by another schema. Generic dominance, a classical notion for measuring information capacity, expresses that every instance of a schema can be uniquely represented in the dominating schema, through application of a deterministic, generic data transformation. Our investigation is motivated both by current interest in schema design for graph databases, as well as by intrinsic scientific interest. We also consider the ternary case, but without inclusion dependencies, and discuss how the notions change in the presence of object identifiers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17664 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the generic information capacity of relational schemas with a single binary relation Groz, Benoît Hidders, Jan Pardal, Nina Bussche, Jan Van den Wieczorek, Piotr Databases 68P15 We consider database schemas consisting of a single binary relation, with key constraints and inclusion dependencies. Over this space of 20 schemas, we completely characterize when one schema is generically dominated by another schema. Generic dominance, a classical notion for measuring information capacity, expresses that every instance of a schema can be uniquely represented in the dominating schema, through application of a deterministic, generic data transformation. Our investigation is motivated both by current interest in schema design for graph databases, as well as by intrinsic scientific interest. We also consider the ternary case, but without inclusion dependencies, and discuss how the notions change in the presence of object identifiers. |
| title | On the generic information capacity of relational schemas with a single binary relation |
| topic | Databases 68P15 |
| url | https://arxiv.org/abs/2603.17664 |