A normal form for XML documents

ABSTRACT

This paper takes a first step towards the design and normalization theory for XML documents. We show that, like relational databases, XML documents may contain redundant information, and may be prone to update anomalies. Furthermore, such problems are caused by certain functional dependencies among paths in the document. Our goal is to find a way of converting an arbitrary DTD into a well-designed one, that avoids these problems. We first introduce the concept of a functional dependency for XML, and define its semantics via a relational representation of XML. We then define an XML normal form, XNF, that avoids update anomalies and redundancies. We study its properties and show that it generalizes BCNF and a normal form for nested relations when those are appropriately coded as XML documents. Finally, we present a lossless algorithm for converting any DTD into one in XNF.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Jürgen Albert , Dora Giammarresi , Derick Wood, Normal form algorithms for extended context-free grammars, Theoretical Computer Science, v.267 n.1-2, p.35-47, 09/26/2001 [doi>10.1016/S0304-3975(00)00294-2]
• 3: Paolo Atzeni , Nicola M. Morfuni, Functional dependencies in relations with null values, Information Processing Letters, v.18 n.4, p.233-238, May 1984 [doi>10.1016/0020-0190(84)90117-0]
• 4: C. Beeri, P. Bernstein, N. Goodman. A sophisticate's introduction to database normalization theory. VLDB'78, pages 113-124.
• 5: 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]
• 6: Peter Buneman , Susan B. Davidson , Wenfei Fan , Carmem S. Hara , Wang Chiew Tan, Reasoning about Keys for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.133-148, September 08-10, 2001
• 7: Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
• 8: DBLP. http://dblp.uni-trier.de/.
• 9: W. F. Dowling and J. H. Gallier. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. JLP 1(3): 267-284 (1984).
• 10: ebXML. Business Process Specification Schema v1.01. http://www.ebxml.org/specs/.
• 11: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.114-125, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375568]
• 12: Wenfei Fan , Jérôme Siméon, Integrity constraints for XML, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.23-34, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335172]
• 13: Mary F. Fernandez , Jérôme Siméon , Philip Wadler, A Semi-monad for Semi-structured Data, Proceedings of the 8th International Conference on Database Theory, p.263-300, January 04-06, 2001
• 14: D. Florescu, D. Kossmann. Storing and querying XML data using an RDMBS. IEEE Data Eng. Bull. 22 (1999), 27-34.
• 15: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 16: Carl A. Gunter, Semantics of programming languages: structures and techniques, MIT Press, Cambridge, MA, 1992
• 17: J. Higgins, R. Jelliffe QAML Version 2.4. http://xml.ascc.net/resource/qaml-xml.dtd, 1999.
• 18: 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]
• 19: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 20: Efficient Storage of XML Data, Proceedings of the 16th International Conference on Data Engineering, p.198, February 28-March 03, 2000
• 21: Mark Levene , George Loizou, Axiomatisation of functional dependencies in incomplete relations, Theoretical Computer Science, v.206 n.1-2, p.283-300, Oct. 6, 1998 [doi>10.1016/S0304-3975(98)80029-7]
• 22: 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]
• 23: 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]
• 24: Yehoshua Sagiv , Claude Delobel , D. Scott Parker, Jr. , Ronald Fagin, An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic, Journal of the ACM (JACM), v.28 n.3, p.435-453, July 1981 [doi>10.1145/322261.322263]
• 25: 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
• 26: Dan Suciu, Bounded fixpoints for complex objects, Theoretical Computer Science, v.176 n.1-2, p.283-328, April 20, 1997 [doi>10.1016/S0304-3975(96)00293-9]
• 27: Zahir Tari , John Stokes , Stefano Spaccapietra, Object normal forms and dependency constraints for object-oriented schemata, ACM Transactions on Database Systems (TODS), v.22 n.4, p.513-569, Dec. 1997 [doi>10.1145/278245.278247]
• 28: 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
• 29: Jan Van den Bussche, Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions, Theoretical Computer Science, v.254 n.1-2, p.363-377, March 6, 2001 [doi>10.1016/S0304-3975(99)00301-1]
• 30: W3C. XML-Data. W3C Note, Jan. 1998.
• 31: W3C. XML Schema. W3C Working Draft, May 2001.
• 32: W3C. XQuery 1.0: An XML Query Language. W3C Working Draft, June 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Design, Languages, Theory