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

ABSTRACT A recently introduced information-theoretic approach toanalyzing redundancies in database design was used to justify normal forms like BCNF that completely eliminateredundancies. The main notion is that of an information content of each datum in an instance (which is a numberin [0, 1]): the closer to 1, the less redundancy it carries. Inpractice, however, one usually settles for 3NF which, un-like BCNF, may not eliminate all redundancies but alwaysguarantees dependency preservation. In this paper we use the information-theoretic approachto 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 measureof redundancy that gets introduced to compensate for de- pendency preservation. This is a number in the [0, 1] range:the smaller it is, the less redundancy a normal form guar- antees. We prove that for every dependency-preservingnormal form, the price of dependency preservation is at least 1/2, and it is precisely 1/2 for 3NF. Hence, 3NF hasthe 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. 1. Introduction In this paper we provide a justification for one of the mostpopular and commonly used normal forms, 3NF. We adopt a recently proposed information-theoretic framework forreasoning about database designs [4]