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

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.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Joseph Albert , Yannis Ioannidis , Raghu Ramakrishnan, Equivalence of keyed relational schemas by conjunctive queries, Journal of Computer and System Sciences, v.58 n.3, p.512-534, June 1999 [doi>10.1006/jcss.1999.1628]
• 3: Marcelo Arenas , Leonid Libkin, A normal form for XML documents, ACM Transactions on Database Systems (TODS), v.29 n.1, p.195-232, March 2004 [doi>10.1145/974750.974757]
• 4: Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Journal of the ACM (JACM), v.52 n.2, p.246-283, March 2005 [doi>10.1145/1059513.1059519]
• 5: C. Beeri, P. Bernstein, and N. Goodman. A sophisticate's introduction to database normalization theory. In VLDB'78, pages 113--124.
• 6: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 7: Joachim Biskup, Achievements of Relational Database Schema Design Theory Revisited, Selected Papers from a Workshop on Semantics in Databases, p.29-54, January 1998
• 8: Roger Cavallo , Michael Pittarelli, The Theory of Probabilistic Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.71-81, September 01-04, 1987
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: Mehmet M. Dalkilic , Edward L. Roberston, Information dependencies, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.245-253, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.336059]
• 11: David W. Embley , Wai Yin Mok, Developing XML Documents with Guaranteed ``Good'' Properties, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.426-441, November 27-30, 2001
• 12: Ronald Fagin, Normal forms and relational database operators, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582120]
• 13: Ronald Fagin, A normal form for relational databases that is based on domains and keys, ACM Transactions on Database Systems (TODS), v.6 n.3, p.387-415, Sept. 1981 [doi>10.1145/319587.319592]
• 14: Richard Hull, Relative information capacity of simple relational database schemata, SIAM Journal on Computing, v.15 n.3, p.856-886, August 1986 [doi>10.1137/0215061]
• 15: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 16: Michael Kifer , Arthur Bernstein , Philip M. Lewis, Database Systems: An Application Oriented Approach, Complete Version (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 17: S. Kolahi. Dependency-preserving normalization of relational and XML data. In DBPL'05.
• 18: Tony T. Lee, An information-theoretic analysis of relational databases—part I: data dependencies and information metric, IEEE Transactions on Software Engineering, v.13 n.10, p.1049-1061, October 1, 1987 [doi>10.1109/TSE.1987.232847]
• 19: Mark Levene , M. Levene , George Loizou, A Guided Tour of Relational Databases and Beyond, Springer-Verlag, London, 1999
• 20: Mark Levene , George Loizou, Why is the snowflake schema a good data warehouse design?, Information Systems, v.28 n.3, p.225-240, May 2003 [doi>10.1016/S0306-4379(02)00021-2]
• 21: Mark Levene , Millist W. Vincent, Justification for Inclusion Dependency Normal Form, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.281-291, March 2000 [doi>10.1109/69.842267]
• 22: Tok-Wang Ling , Frank W. Tompa , Tiko Kameda, An improved third normal form for relational databases, ACM Transactions on Database Systems (TODS), v.6 n.2, p.329-346, June 1981 [doi>10.1145/319566.319583]
• 23: Oracle's General Database Design FAQ. http://www.orafaq.com/faqdesgn.htm.
• 24: Victor Vianu, A Web Odyssey: from Codd to XML, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-15, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375554]
• 25: Carlo Zaniolo, A new normal form for the design of relational database schemata, ACM Transactions on Database Systems (TODS), v.7 n.3, p.489-499, Sept. 1982 [doi>10.1145/319732.319749]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Value of information; Information theory
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

General Terms:
Design, Theory