An information-theoretic approach to normal forms for relational and XML data

ABSTRACT

Normalization as a way of producing good relational database designs is a well-understood topic. However, the same problem of distinguishing well-designed databases from poorly designed ones arises in other data models, in particular, XML. While, in the relational world, the criteria for being well designed are usually very intuitive and clear to state, they become more obscure when one moves to more complex data models.Our goal is to provide a set of tools for testing when a condition on a database design, specified by a normal form, corresponds to a good design. We use techniques of information theory, and define a measure of information content of elements in a database with respect to a set of constraints. We first test this measure in the relational context, providing information-theoretic justification for familiar normal forms such as BCNF, 4NF, PJ/NF, 5NFR, DK/NF. We then show that the same measure applies in the XML context, which gives us a characterization of a recently introduced XML normal form called XNF. Finally, we look at information-theoretic criteria for justifying normalization algorithms.

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, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543625]
• 4: 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]
• 5: Beeri, C., Bernstein, P., and Goodman, N. 1978. A sophisticate's introduction to database normalization theory. In Proceedings of the 4th International Conference on Very Large Data Bases. 113--124.
• 6: Joachim Biskup, Achievements of Relational Database Schema Design Theory Revisited, Selected Papers from a Workshop on Semantics in Databases, p.29-54, January 1998
• 7: 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
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: 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]
• 10: 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
• 11: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• 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: 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]
• 17: 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]
• 18: 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]
• 19: Ley, M. 2003. DBLP. http://www.informatik.uni-trier.de/~ley/db/index.html.
• 20: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 21: Wai Yin Mok , Yiu-Kai Ng , David W. Embley, A normal form for precisely characterizing redundancy in nested relations, ACM Transactions on Database Systems (TODS), v.21 n.1, p.77-106, March 1996 [doi>10.1145/227604.227612]
• 22: Z. Meral Ozsoyoglu , Li-Yan Yuan, A new normal form for nested relations, ACM Transactions on Database Systems (TODS), v.12 n.1, p.111-136, March 1987 [doi>10.1145/12047.13676]
• 23: Papadimitriou, C. 1994. Computational complexity. Addison-Wesley, Reading, Mass.
• 24: Shannon, C. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 379--423 (Part I), 623--656 (Part II).
• 25: Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603874]
• 26: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 27: 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]
• 28: Millist W. Vincent, A corrected 5NF definition for relational database design, Theoretical Computer Science, v.185 n.2, p.379-391, Oct. 20, 1997 [doi>10.1016/S0304-3975(97)00050-9]
• 29: Vincent, M. 1999. Semantic foundations of 4NF in relational database design. Acta Inf. 36, 3, 173--213.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

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

General Terms:
Design, Management, Theory

Keywords:
Information theory, XML, design, normal forms, normalization algorithms, relational databases