XML design for relational storage

ABSTRACT

Design principles for XML schemas that eliminate redundancies and avoid update anomalies have been studied recently. Several normal forms, generalizing those for relational databases, have been proposed. All of them, however, are based on the assumption of anative XML storage, while in practice most of XML data is stored inrelational databases.

In this paper we study XML design and normalization for relational storage of XML documents. To be able to relate and compare XML and relational designs, we use an information-theoretic framework that measures information content in relations and documents, with higher values corresponding to lower levels of redundancy. We show that most common relational storage schemes preserve the notion of being well-designed (i.e., anomalies- and redundancy-free). Thus,existing XML normal forms guarantee well-designed relational storagesas well. We further show that if this perfect option is not achievable, then a slight restriction on XML constraints guarantees a "second-best" relational design, according to possible values of the information-theoretic measure. We finally consider an edge-based relational representation of XML documents, and show that while it has similar information-theoretic properties with other relational representations, it can behave significantly worse in terms of enforcing integrity constraints.

REFERENCES

• 1: Xyleme XML server & business document management. http://www.xyleme.com/page/xml storage/.
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: Marcelo Arenas , Wenfei Fan , Leonid Libkin, On verifying consistency of XML specifications, 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.543647]
• 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: 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]
• 6: Denilson Barbosa , Juliana Freire , Alberto O. Mendelzon, Designing information-preserving mapping schemes for XML, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: C. Beeri, P. A. Bernstein, and N. Goodman. A sophisticate's introduction to database normalization theory. In VLDB, pages 113--124, 1978.
• 8: 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]
• 9: Joachim Biskup, Achievements of Relational Database Schema Design Theory Revisited, Selected Papers from a Workshop on Semantics in Databases, p.29-54, January 1998
• 10: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 11: 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
• 12: E. F. Codd. Normalized database structure: A brief tutorial. In ACM SIGFIDET Workshop on Data Description, Access and Control, 1971.
• 13: E. F. Codd. Further normalization of data base relational model. In Courant Computer Science Symposium 6: Data Base Systems, pages 33--64, 1972.
• 14: E. F. Codd. Recent investigations in relational database systems. In Information Processing, pages 1017--1021, 1974.
• 15: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 16: 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]
• 17: S. Davidson, W. Fan, C. Hara, and J. Qin. Propagating XML constraints to relations. In ICDE, pages 543--554, 2003.
• 18: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 19: A. Deutsch and V. Tannen. MARS: A system for publishing XML from mixed and redundant storage. In VLDB, pages 201--212, 2003.
• 20: 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
• 21: D. Florescu and D. Kossmann. Storing and querying XML data using an RDBMS. IEEE Data Eng. Bulletin, 22(3):27--34, 1999.
• 22: P. C. Kanellakis. Elements of relational database theory. pages 1073--1156, 1990.
• 23: Carl-Christian Kanne , Guido Moerkotte, A linear time algorithm for optimal tree sibling partitioning and approximation algorithms in Natix, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 24: 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
• 25: Solmaz Kolahi , Leonid Libkin, On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142369]
• 26: R. Krishnamurthy, R. Kaushik, and J. F. Naughton. XML-to-SQL query translation literature: The state of the art and open problems. In XSym'03, LNCS 28--24, pages 118, 2003.
• 27: Tony T. Lee, An Infornation-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 1987 [doi>10.1109/TSE.1987.232847]
• 28: Mark Levene , M. Levene , George Loizou, A Guided Tour of Relational Databases and Beyond, Springer-Verlag, London, 1999
• 29: 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]
• 30: Zhen Hua Liu , Muralidhar Krishnaprasad , Vikas Arora, Native Xquery processing in oracle XMLDB, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066259]
• 31: Matthias Nicola , Bert van der Linden, Native XML support in DB2 universal database, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 32: Albrecht Schmidt , Martin L. Kersten , Menzo Windhouwer , Florian Waas, Efficient Relational Storage and Retrieval of XML Documents, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.137-150, May 18-19, 2000
• 33: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 34: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 35: M. W. Vincent and J. Liu. Functional dependencies for XML. In APWEB, pages 22--34, 2003.
• 36: M. W. Vincent, J. Liu, and C. Liu. A redundancy free 4NF for XML. In XSym, pages 254--266, 2003.
• 37: Millist W. Vincent , Jixue Liu , Chengfei Liu, Strong functional dependencies and their application to normal forms in XML, ACM Transactions on Database Systems (TODS), v.29 n.3, p.445-462, September 2004 [doi>10.1145/1016028.1016029]
• 38: Junhu Wang , Rodney Topor, Removing XML data redundancies using functional and equality-generating dependencies, Proceedings of the 16th Australasian database conference, p.65-74, January 01, 2005, Newcastle, Australia
• 39: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]
• 40: 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
      H.2.1 Logical Design
          Subjects: Normal forms

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory; Value of information

General Terms:
Design, Management, Theory

Keywords:
XML data, design, equality-generating dependencies, functional dependencies, information theory, relational storage