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.1085318e-05
Overall Rank: 3,422 | 76.22%
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,912	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	0.00010116822
3,782	Bag Query Containment and Information Theory	2020	PODS	6.7691169e-05
8,046	Information Theory for Data Management	2010	SIGMOD	4.5949091e-05
9,178	RRXS: Redundancy reducing XML storage in relations	2003	VLDB	4.3796483e-05
10,250	Structural Normalization of Property Graphs	2026	VLDB	4.1905499e-05
12,363	Information Theory For Data Management	2009	VLDB	4.1905499e-05
12,495	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.1905499e-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.0007528369
303	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00028289399
453	The Theory Of Probabilistic Databases	1987	VLDB	0.00022801484
1,051	A Normal Form for Nested Relations	1985	PODS	0.00014421811
1,820	A Normal Form for XML Documents	2002	PODS	0.00010410152
1,886	Normal forms and relational database operators	1979	SIGMOD	0.00010205841
3,051	Updating XML	2001	SIGMOD	7.6489131e-05
3,245	Information Dependencies	2000	PODS	7.324637e-05
4,014	A Web Odyssey: from Codd to XML	2001	PODS	6.5300582e-05
5,710	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS	5.3619696e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,912	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	0.00010116822
6,940	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB	4.8878659e-05
14,380	A Constructive Definition Of Third Normal Form	1976	SIGMOD	-
12,808	Normalizing Incomplete Databases	1995	PODS	4.1905499e-05
3,086	Reflections on Boyce-Codd Normal Form	1982	VLDB	7.5948483e-05
10,517	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.1905499e-05
11,494	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	4.1905499e-05
11,862	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	4.1905499e-05
12,495	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.1905499e-05
1,820	A Normal Form for XML Documents	2002	PODS	0.00010410152