An Information-Theoretic Approach to Normal Forms for Relational and XML Data

Summary: Propose an information-theoretic measure of element information relative to constraints to justify classic relational normal forms (BCNF, 4NF, PJ/NF, 5NF, DK/NF) and to evaluate normalization algorithms. Extend same framework to XML to characterize XNF and provide a unified quantitative foundation for deciding and deriving good designs across relational and XML models. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1274
Venue: PODS
Year: 2003
Pagerank: 7.4182332e-05
Overall Rank: 3,432 | 76.46%
DOI: 10.1145/773153.773155

Incoming Non-self Citations Over Time

Authors

1. Marcelo Arenas (University of Toronto)
2. Leonid Libkin (University of Toronto)

BibTeX Citation

@inproceedings{arenas_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{An Information-Theoretic Approach to Normal Forms for Relational and XML Data}},
        url = {https://dl.acm.org/doi/10.1145/773153.773155},
        doi = {10.1145/773153.773155},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arenas, Marcelo and Libkin, Leonid},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	9.4928569e-05
3,457	Bag Query Containment and Information Theory	2020	PODS	7.3981641e-05
8,405	Information Theory for Data Management	2010	SIGMOD	5.4323037e-05
9,347	RRXS: Redundancy reducing XML storage in relations	2003	VLDB	5.2843327e-05
10,538	Structural Normalization of Property Graphs	2026	VLDB	5.093636e-05
12,548	Information Theory For Data Management	2009	VLDB	5.093636e-05
12,679	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
413	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018894294
557	The Theory of Probabilistic Databases	1987	VLDB	0.00016541752
1,056	A Normal Form for Nested Relations	1985	PODS	0.00012388199
1,671	A Normal Form for XML Documents	2002	PODS	0.00010043595
2,422	Normal forms and relational database operators	1979	SIGMOD	8.6023273e-05
2,772	Updating XML	2001	SIGMOD	8.1398108e-05
3,141	Information Dependencies	2000	PODS	7.7170066e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
5,643	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS	6.1379759e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
2	7,542	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB
3	14,567	A Constructive Definition Of Third Normal Form	1976	SIGMOD
4	12,993	Normalizing Incomplete Databases	1995	PODS
5	3,437	Reflections on Boyce-Codd Normal Form	1982	VLDB
6	10,781	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD
7	11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD
8	12,055	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
9	12,679	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS
10	1,671	A Normal Form for XML Documents	2002	PODS