Multivalued Dependencies in XML

  • Millist W. Vincent
  • Jixue Liu
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2712)


Functional dependencies (FDs) and multivalued dependencies (MVDs) play a fundamental role in relational databases where they provide semantics for the data and at the same time are the foundation for database design. Since XML documents are closely coupled with relational databases in that XML documents are typically exported and imported from relational databases, the study of FDs and MVDs in XML is of fundamental significance in XML research. In this paper we investigate the issue of defining multivalued dependencies in XML, a topic which to the best of our knowledge has not been previously investigated. We define multivalued dependencies in XML (XMVDs) and justify our definition by proving that, for a very general class of mappings from relations to XML, a relation satisfies an MVD if and only if the corresponding XML document satisfies the corresponding XMVD. Thus our definition of a XMVD in a XML document is a natural extension of the definition of a MVD in relations.


Relational Database Integrity Constraint Database Design High Order Attribute Semistructured Data 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web. Morgan Kauffman, 2000.Google Scholar
  2. 2.
    M. Arenas and L. Libkin. A normal form for xml documents. In Proc. ACM PODS Conference, pages 85–96, 2002.Google Scholar
  3. 3.
    P. Atzeni and V. DeAntonellis. Foundations of databases. Benjamin Cummings, 1993.Google Scholar
  4. 4.
    C. Beeri, R. Fagin, and J.H. Howard. A complete exiomatization for functional and multivalued dependencies. In ACM SIGMOD Conference, pages 47–61, 1977.Google Scholar
  5. 5.
    P. Buneman, S. Davidson, W. Fan, and C. Hara. Reasoning about keys for xml. In International Workshop on Database Programming Languages, 2001.Google Scholar
  6. 6.
    P. Buneman, S. Davidson, W. Fan, C. Hara, and W. Tan. Keys for xml. Computer Networks, 39(5):473–487, 2002.CrossRefGoogle Scholar
  7. 7.
    P. Buneman, W. Fan, J. Simeon, and S. Weinstein. Constraints for semistructured data and xml. ACM SIGMOD Record, 30(1):45–47, 2001.CrossRefGoogle Scholar
  8. 8.
    P. Buneman, W. Fan, and S. Weinstein. Path constraints on structured and semistructured data. In Proc. ACM PODS Conference, pages 129–138, 1998.Google Scholar
  9. 9.
    W. Fan and J. Simeon. Integrity constraints for xml. In Proc. ACM PODS Conference, pages 23–34, 2000.Google Scholar
  10. 10.
    M. Levene and G. Loizu. Axiomatization of functional dependencies in incomplete relations. Theoretical Computer Science, 206:283–300, 1998.zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    M. Levene and G. Loizu. A guided tour of relational databases and beyond. Springer, 1999.Google Scholar
  12. 12.
    J. Shanmugasundaram, K. Tufte, C. Zhang, G. He, D. J. DeWitt, and J. F. Naughton:. Relational databases for querying xml documents: Limitations and opportunities. In VLDB Conference, pages 302–314, 1999.Google Scholar
  13. 13.
    S.J. Thomas and P.C. Fischer. Nested relational structures. In P. Kanellakis, editor, The theory of databases, pages 269–307. JAI Press, 1986.Google Scholar
  14. 14.
    M. W. Vincent and M. Levene. Restructuring partitioned normal relations without information loss. SIAM Journal on Computing, 39(5):1550–1567, 2000.CrossRefMathSciNetGoogle Scholar
  15. 15.
    M.W. Vincent and J. Liu. Strong functional dependencies and a redundancy free normal form for xml. Submitted for publication, 2002.Google Scholar
  16. 16.
    M.W. Vincent and J. Liu. Functional dependencies for xml. In Fifth Asian Pacific Web Conference, 2003.Google Scholar
  17. 17.
    M.W. Vincent and J. Liu. Multivalued dependencies and a 4nf for xml. In 15th CAISE Conference, 2003.Google Scholar
  18. 18.
    J. Widom. Data management for xml-research directions. IEEE data Engineering Bulletin, 22(3):44–52, 1999.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Millist W. Vincent
    • 1
  • Jixue Liu
    • 1
  1. 1.School of Computer and Information ScienceUniversity of South AustraliaAustralia

Personalised recommendations