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: 1383
Venue: PODS
Year: 2006
Pagerank: 4.1905499e-05
Overall Rank: 12,495 | 13.16%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Solmaz Kolahi
2. Leonid Libkin

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
303	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00028289399
453	The Theory Of Probabilistic Databases	1987	VLDB	0.00022801484
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,245	Information Dependencies	2000	PODS	7.324637e-05
3,422	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.1085318e-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,820	A Normal Form for XML Documents	2002	PODS	0.00010410152
1,912	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	0.00010116822
6,182	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.1637091e-05
5,911	Normalizing Property Graphs	2023	VLDB	5.2718035e-05
3,086	Reflections on Boyce-Codd Normal Form	1982	VLDB	7.5948483e-05
11,176	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD	4.1905499e-05
11,494	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	4.1905499e-05
3,422	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.1085318e-05
11,862	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	4.1905499e-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