Article

Designing Functional Dependencies for XML

Authors:

Wai Lup LowAuthors Info & Claims

EDBT '02: Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology

Pages 124 - 141

Published: 25 March 2002 Publication History

Abstract

Functional dependencies are an integral part of database theory and they form the basis for normalizing relational tables up to BCNF. With the increasing relevance of the data-centric aspects of XML, it is pertinent to study functional dependencies in the context of XML, which will form the basis for further studies into XML keys and normalization. In this work, we investigate the design of functional dependencies in XML databases. We propose FD _XML, a notation and DTD for representing functional dependencies in XML. We observe that many databases are hierarchical in nature and the corresponding nested XML data may inevitably contain redundancy. We develop a model based on FD _XML to estimate the amount of data replication in XML data. We show how functional dependencies in XML can be verified with a single pass through the XML data, and present supporting experimental results. A platform-independent framework is also drawn up to demonstrate how the techniques proposed in this work can enrich the semantics of XML.

References

[1]

W. W. Armstrong. Dependency Structures of Database Relationships. In Proceedings of the tri-annual IFIP Conf 74, N-H (Amsterdam) , 1974.

[2]

Peter Bunemana, Susan Davidson, Wenfei Fan, Carmem Hara, and Wang-Chiew Tan. Keys for XML. In Proceedings of the WWW'10, Hong Kong, China , 2001.

[3]

P. A. Bernstein. Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Transactions on Database Systems , 1(4):277- 298, Dec 1976.

[4]

Tim Bray, Jean Paoli, C. M. Sperberg-McQueen, and Eve Maler. Extensible Markup Language (XML) 1.0 (Second Edition). http://www.w3.org/TR/2000/REC-xml-20001006, 2000.

[5]

James Clark and Steve DeRose. XML Path Language (XPath) Version 1.0. Available at http://www.w3.org/TR/xpath, 1999.

[6]

E. F. Codd. A Relational Model of Data for Large Shared Data Banks. j-CA CM , 13(6):377-387, June 1970.

[7]

E. F. Codd. Further Normalization of the Database Relational Model . R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, NJ, 1972.

[8]

Dongwon Lee and Wesley W. Chu. Comparative Analysis of Six XML Schema Languages. SIGMOD Record , 29(3):76--87, 2000.

[9]

D. Fallside. XML Schema Part 0: Primer. Available at http://www.w3.org/TR/xmlschema-0/, 2000.

[10]

Mary Fernandez and Jonathan Robie. XML Query Data Model. W3C Working Draft. Available at http://www.w3.org/TR/query-datamodel/, 2001.

[11]

W. Fan and J. Siméon. Integrity Constraints for XML. In Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Dallas, Texas, USA , pages. 23-34. ACM, 2000.

[12]

Dongwon Lee and Wesley W. Chu. Constraints-Preserving Transformation from XML Document Type Definition to Relational Schema. In Proceedings of the 19th International Conference on Conceptual Modeling , pages. 323-338, 2000.

[13]

Michael Ley. DBLP Bibliography. Available at http://www.informatik.uni-trier.de/ley/db/, 2001.

[14]

Tok Wang Ling, Cheng Hian Goh, and Mong Li Lee. Extending classical functional dependencies for physical database design. Information and Software Technology , 9(38):601-608, 1996.

[15]

J. McHugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom. Lore: A Database Management System for Semistructured Data. SIGMOD Record , 26(3), 1997.

[16]

David Megginson. SAX: The Simple API for XML. Available at http://www.megginson.com/SAX/, 2001.

[17]

The Apache XML Project. Xerces Java Parser. Available at http://xml.apache.org/xerces-j/index.html, 2001.

[18]

Tsou and Fischer. Decomposition of a Relation Scheme into Boyce-Codd Normal Form. SIGACTN: SIGACT News , 14, 1982.

[19]

Kevin Williams et al. Professional XML Databases . Wrox Press Inc, 2000.

[20]

W3C DOM Working Group. Document Object Model (DOM). Available at http://www.w3.org/DOM/, 2001.

[21]

Grant E. Weddell. Reasoning About Functional Dependencies Generalized for Semantic Data Models. ACM Transactions on Database Systems , 17(1):32-64, Mar 1992.

[22]

Jennifer Widom. Data Management for XML: Research Directions. IEEE Data Engineering Bulletin , 22(3):44-52, 1999.

[23]

Xiaoying Wu, Tok Wang Ling, Mong Li Lee, and Gillian Dobbie. Designing Semistructured Databases Using the ORA-SS Model. In Proceedings of the 2nd International Conference on Web Information Systems Engineering (WISE) . IEEE Computer Society, 2001.

Cited By

Niewerth MSchwentick T(2018)Reasoning About XML Constraints Based on XML-to-Relational MappingsTheory of Computing Systems10.1007/s00224-018-9846-562:8(1826-1879)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00224-018-9846-5
Caruccio LDeufemia VPolese GDesai BToyama MBernardino J(2016)On the Discovery of Relaxed Functional DependenciesProceedings of the 20th International Database Engineering & Applications Symposium10.1145/2938503.2938519(53-61)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2938503.2938519
Bouchou BHalfeld-Ferrari MLima M(2012)A grammarware for the incremental validation of integrity constraints on XML documents under multiple updatesTransactions on Large-Scale Data- and Knowledge-Centered Systems VI10.5555/2407076.2407082(167-197)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2407076.2407082
Show More Cited By

Designing Functional Dependencies for XML
1. Applied computing
  1. Document management and text processing
2. Information systems
  1. Data management systems

Recommendations

A Survey Study on XML Functional Dependencies
ISDPE '07: Proceedings of the The First International Symposium on Data, Privacy, and E-Commerce

There are two major kinds of XML functional dependency (FD) definitions. The first kind of XML FD includes Tree-tuple-based XML FD (tFD) and Path-based XML FD (pFD), and the second kind of XML FD includes Extended-path-based XML FD (epFD), Sub-graph-...
Functional dependencies for XML
WAIM'10: Proceedings of the 2010 international conference on Web-age information management

In this paper, we present a new approach for defining functional dependencies for XML (XFDs) on XML Schema. While showing how to extend XML Schema, we analyze the expressive power of our XFDs. We focus on supporting complex value (e.g. list, set) in our ...
Local XML functional dependencies
WIDM '03: Proceedings of the 5th ACM international workshop on Web information and data management

Keys and functional dependencies play a fundamental role in relational databases where they are used in integrity enforcement and in database design. Similarly, these constraints will play a fundamental role in XML and recently keys and functional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EDBT '02: Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology

March 2002

774 pages

ISBN:3540433244

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 25 March 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Niewerth MSchwentick T(2018)Reasoning About XML Constraints Based on XML-to-Relational MappingsTheory of Computing Systems10.1007/s00224-018-9846-562:8(1826-1879)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00224-018-9846-5
Caruccio LDeufemia VPolese GDesai BToyama MBernardino J(2016)On the Discovery of Relaxed Functional DependenciesProceedings of the 20th International Database Engineering & Applications Symposium10.1145/2938503.2938519(53-61)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2938503.2938519
Bouchou BHalfeld-Ferrari MLima M(2012)A grammarware for the incremental validation of integrity constraints on XML documents under multiple updatesTransactions on Large-Scale Data- and Knowledge-Centered Systems VI10.5555/2407076.2407082(167-197)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2407076.2407082
Sadiq SYeganeh NIndulska M(2011)20 years of data quality researchProceedings of the Twenty-Second Australasian Database Conference - Volume 11510.5555/2460396.2460415(153-162)Online publication date: 17-Jan-2011
https://dl.acm.org/doi/10.5555/2460396.2460415
Yu YHeflin J(2011)Extending functional dependency to detect abnormal data in RDF graphsProceedings of the 10th international conference on The semantic web - Volume Part I10.5555/2063016.2063067(794-809)Online publication date: 23-Oct-2011
https://dl.acm.org/doi/10.5555/2063016.2063067
Hartmann SKöhler HTrinh T(2010)On the Existence of Armstrong Data Trees for XML Functional DependenciesProceedings of the 6th International Symposium on Foundations of Information and Knowledge Systems - Volume 595610.5555/2961313.2961324(94-113)Online publication date: 15-Feb-2010
https://dl.acm.org/doi/10.5555/2961313.2961324
Chen HLiao HGao Z(2010)Functional dependencies for XMLProceedings of the 2010 international conference on Web-age information management10.5555/1927585.1927598(110-115)Online publication date: 15-Jul-2010
https://dl.acm.org/doi/10.5555/1927585.1927598
Shi HAmagasa TKitagawa H(2010)Fast detection of functional dependencies in XML dataProceedings of the 7th international XML database conference on Database and XML technologies10.5555/1888011.1888025(113-127)Online publication date: 17-Sep-2010
https://dl.acm.org/doi/10.5555/1888011.1888025
Shahriar MLiu J(2009)On the Performances of Checking XML Key and Functional Dependency SatisfactionsProceedings of the Confederated International Conferences, CoopIS, DOA, IS, and ODBASE 2009 on On the Move to Meaningful Internet Systems: Part II10.1007/978-3-642-05151-7_37(1254-1271)Online publication date: 7-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-05151-7_37
Saito TMorishita SLakshmanan LNg RShasha D(2008)Relational-style XML queryProceedings of the 2008 ACM SIGMOD international conference on Management of data10.1145/1376616.1376650(303-314)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1376616.1376650
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents