On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF

Solmaz Kolahi, Leonid Libkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A recently introduced information-theoretic approach to analyzing redundancies in database design was used to justify normal forms like BCNF that completely eliminate redundancies. The main notion is that of an information content of each datum in an instance (which is a number in [0,1]): the closer to 1, the less redundancy it carries. In practice, however, one usually settles for 3NF which, unlike BCNF, may not eliminate all redundancies but always guarantees dependency preservation.In this paper we use the information-theoretic approach to prove that 3NF is the best normal form if one needs to achieve dependency preservation. For each dependency-preserving normal form, we define the price of dependency preservation as an information-theoretic measure of redundancy that gets introduced to compensate for dependency preservation. This is a number in the [0,1] range: the smaller it is, the less redundancy a normal form guarantees. We prove that for every dependency-preserving normal form, the price of dependency preservation is at least 1/2, and it is precisely 1/2 for 3NF. Hence, 3NF has the least amount of redundancy among all dependency-preserving normal forms. We also show that, information-theoretically, unnormalized schemas have at least twice the amount of redundancy than schemas in 3NF.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA
PublisherACM
Pages114-123
Number of pages10
ISBN (Electronic)1-59593-318-2
DOIs
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF'. Together they form a unique fingerprint.

Cite this