On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF

Summary: Propose an information-theoretic "price of dependency preservation" (in [0,1]) measuring redundancy added to preserve FDs; prove any dependency-preserving normal form has price ≥ 1/2. Show 3NF attains price = 1/2 (optimal), and unnormalized schemas incur ≥2× the redundancy of 3NF. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1382
Venue: PODS
Year: 2006
Pagerank: 5.093636e-05
Overall Rank: 12,679 | 13.02%
DOI: 10.1145/1142351.1142369

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Solmaz Kolahi (University of Toronto)
2. Leonid Libkin (University of Edinburgh; University of Toronto)

BibTeX Citation

@inproceedings{kolahi_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142369},
        doi = {10.1145/1142351.1142369},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolahi, Solmaz and Libkin, Leonid},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
413	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018894294
557	The Theory of Probabilistic Databases	1987	VLDB	0.00016541752
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
3,141	Information Dependencies	2000	PODS	7.7170066e-05
3,432	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.4182332e-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,671	A Normal Form for XML Documents	2002	PODS
2	1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
3	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
4	5,690	Normalizing Property Graphs	2023	VLDB
5	3,437	Reflections on Boyce-Codd Normal Form	1982	VLDB
6	11,379	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD
7	11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD
8	3,432	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS
9	12,055	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
10	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