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: h108cd37fc4ae07cb
Venue: PODS
Year: 2003
Pagerank: 7.2252535e-05
Overall Rank: 3,514 | 76.45%
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,979	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	9.2615384e-05
3,533	Bag Query Containment and Information Theory	2020	PODS	7.204863e-05
8,587	Information Theory for Data Management	2010	SIGMOD	5.2938507e-05
9,563	RRXS: Redundancy reducing XML storage in relations	2003	VLDB	5.1462732e-05
10,791	Structural Normalization of Property Graphs	2026	VLDB	4.9605343e-05
12,887	Information Theory For Data Management	2009	VLDB	4.9605343e-05
13,017	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.9605343e-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
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045733094
428	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018419906
573	The Theory of Probabilistic Databases	1987	VLDB	0.00016152578
1,087	A Normal Form for Nested Relations	1985	PODS	0.00012067301
1,708	A Normal Form for XML Documents	2002	PODS	9.8029408e-05
2,482	Normal forms and relational database operators	1979	SIGMOD	8.3846066e-05
2,846	Updating XML	2001	SIGMOD	7.9272482e-05
3,201	Information Dependencies	2000	PODS	7.5247986e-05
4,281	A Web Odyssey: from Codd to XML	2001	PODS	6.6721591e-05
5,758	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS	5.9861388e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,979	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
2	7,707	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB
3	14,910	A Constructive Definition Of Third Normal Form	1976	SIGMOD
4	13,330	Normalizing Incomplete Databases	1995	PODS
5	3,484	Reflections on Boyce-Codd Normal Form	1982	VLDB
6	9,992	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	10,004	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD
8	10,007	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
9	13,017	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS
10	1,708	A Normal Form for XML Documents	2002	PODS