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: 1275
Venue: PODS
Year: 2003
Pagerank: 7.1154446e-05
Overall Rank: 3,420 | 76.21%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Marcelo Arenas
2. Leonid Libkin

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,908	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	0.00010126101
3,775	Bag Query Containment and Information Theory	2020	PODS	6.775636e-05
8,044	Information Theory for Data Management	2010	SIGMOD	4.5993522e-05
9,174	RRXS: Redundancy reducing XML storage in relations	2003	VLDB	4.3838473e-05
10,250	Structural Normalization of Property Graphs	2026	VLDB	4.1945683e-05
12,355	Information Theory For Data Management	2009	VLDB	4.1945683e-05
12,486	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.1945683e-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
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00075110004
302	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00028316973
450	The Theory Of Probabilistic Databases	1987	VLDB	0.00022822073
1,052	A Normal Form for Nested Relations	1985	PODS	0.00014436103
1,803	A Normal Form for XML Documents	2002	PODS	0.00010504331
1,884	Normal forms and relational database operators	1979	SIGMOD	0.00010215563
3,046	Updating XML	2001	SIGMOD	7.65634e-05
3,240	Information Dependencies	2000	PODS	7.3316755e-05
4,010	A Web Odyssey: from Codd to XML	2001	PODS	6.5351699e-05
5,697	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS	5.3671336e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,908	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	0.00010126101
6,938	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB	4.8925595e-05
14,366	A Constructive Definition Of Third Normal Form	1976	SIGMOD	-
12,799	Normalizing Incomplete Databases	1995	PODS	4.1945683e-05
3,111	Reflections on Boyce-Codd Normal Form	1982	VLDB	7.5474137e-05
10,508	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	4.1945683e-05
11,490	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	4.1945683e-05
11,854	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	4.1945683e-05
12,486	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.1945683e-05
1,803	A Normal Form for XML Documents	2002	PODS	0.00010504331