On the generic information capacity of relational schemas with a single binary relation

Benoît Groz; Jan Hidders; Nina Pardal; Jan Van den Bussche; Piotr Wieczorek

doi:10.48550/arXiv.2603.17664

On the generic information capacity of relational schemas with a single binary relation

Benoît Groz
, Jan Hidders^*
, Nina Pardal
, Jan Van den Bussche
, Piotr Wieczorek

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 2027 EDBT/ICDT Joint Conference
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-27
Number of pages	27
DOIs	https://doi.org/10.48550/arXiv.2603.17664
Publication status	Accepted/In press - 28 May 2026
Event	30th International Conference on Database Theory - Lille, France Duration: 6 Apr 2027 → 9 Apr 2027 Conference number: 30 https://edbticdt2027.github.io/

Publication series

Name	Leibniz International Proceedings in Informatics
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik
ISSN (Electronic)	1868-8969

Conference

Conference	30th International Conference on Database Theory
Abbreviated title	ICDT 2027
Country/Territory	France
City	Lille
Period	6/04/27 → 9/04/27
Internet address	https://edbticdt2027.github.io/

Access to Document

10.48550/arXiv.2603.17664

GrozEtalICDT2027OntheGenericInformationCapacityAccepted author manuscript, 934 KB

Cite this

Groz, B., Hidders, J., Pardal, N., Van den Bussche, J., & Wieczorek, P. (Accepted/In press). On the generic information capacity of relational schemas with a single binary relation. In Proceedings of the 2027 EDBT/ICDT Joint Conference (pp. 1-27). (Leibniz International Proceedings in Informatics). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.48550/arXiv.2603.17664

@inproceedings{7ac4ce9718134f589437e0451cfe60f4,

title = "On the generic information capacity of relational schemas with a single binary relation",

abstract = "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.",

author = "Beno{\^i}t Groz and Jan Hidders and Nina Pardal and \{Van den Bussche\}, Jan and Piotr Wieczorek",

year = "2026",

month = may,

day = "28",

doi = "10.48550/arXiv.2603.17664",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--27",

booktitle = "Proceedings of the 2027 EDBT/ICDT Joint Conference",

note = "30th International Conference on Database Theory, ICDT 2027 ; Conference date: 06-04-2027 Through 09-04-2027",

url = "https://edbticdt2027.github.io/",

}

Groz, B, Hidders, J, Pardal, N, Van den Bussche, J & Wieczorek, P 2026, On the generic information capacity of relational schemas with a single binary relation. in Proceedings of the 2027 EDBT/ICDT Joint Conference. Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-27, 30th International Conference on Database Theory, Lille, France, 6/04/27. https://doi.org/10.48550/arXiv.2603.17664

On the generic information capacity of relational schemas with a single binary relation. / Groz, Benoît; Hidders, Jan; Pardal, Nina et al.
Proceedings of the 2027 EDBT/ICDT Joint Conference. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. p. 1-27 (Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the generic information capacity of relational schemas with a single binary relation

AU - Groz, Benoît

AU - Hidders, Jan

AU - Pardal, Nina

AU - Van den Bussche, Jan

AU - Wieczorek, Piotr

N1 - Conference code: 30

PY - 2026/5/28

Y1 - 2026/5/28

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

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

U2 - 10.48550/arXiv.2603.17664

DO - 10.48550/arXiv.2603.17664

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 27

BT - Proceedings of the 2027 EDBT/ICDT Joint Conference

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 30th International Conference on Database Theory

Y2 - 6 April 2027 through 9 April 2027

ER -

On the generic information capacity of relational schemas with a single binary relation

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this