XML schema mappings

ABSTRACT

Relational schema mappings have been extensively studied in connection with data integration and exchange problems, but mappings between XML schemas have not received the same amount of attention. Our goal is to develop a theory of expressive XML schema mappings. Such mappings should be able to use various forms of navigation in a document, and specify conditions on data values. We develop a language for XML schema mappings, and concentrate on three types of problems: static analysis of mappings, their complexity, and their composition. We look at static analysis problems related to various flavors of consistency: for example, whether it is possible to map some document of a source schema into a document of the target schema, or whether all documents of a source schema can be mapped. We classify the complexity of these problems. We then move to the complexity of mappings themselves, i.e., recognizing pairs of documents such that one can be mapped into the other, and provide a classification based on sets of features used in mappings. Finally we look at composition of XML schema mappings. We study its complexity and show that it is harder to achieve closure under composition for XML than for relational mappings. Nevertheless, we find a robust class of XML schema mappings that have good complexity properties and are closed under composition.

REFERENCES

• 1: Serge Abiteboul , Luc Segoufin , Victor Vianu, Representing and querying XML with incomplete information, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.150-161, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375571]
• 2: S. Amer-Yahia , S. Cho , L. V. S. Lakshmanan , D. Srivastava, Tree pattern query minimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.315-331, December 2002 [doi>10.1007/s00778-002-0076-7]
• 3: 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]
• 4: Marcelo Arenas , Leonid Libkin, XML data exchange: Consistency and query answering, Journal of the ACM (JACM), v.55 n.2, p.1-72, May 2008 [doi>10.1145/1346330.1346332]
• 5: Marcelo Arenas , Jorge Pérez , Cristian Riveros, The recovery of a schema mapping: bringing exchanged data back, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376920]
• 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: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM (JACM), v.55 n.2, p.1-79, May 2008 [doi>10.1145/1346330.1346333]
• 8: Philip A. Bernstein , Todd J. Green , Sergey Melnik , Alan Nash, Implementing mapping composition, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 9: Philip A. Bernstein , Sergey Melnik, Model management 2.0: manipulating richer mappings, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247482]
• 10: Geert Jan Bex , Frank Neven , Jan Van den Bussche, DTDs versus XML schema: a practical study, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017095]
• 11: Mikolaj Bojańczyk , Claire David , Anca Muscholl , Thomas Schwentick , Luc Segoufin, Two-variable logic on data trees and XML reasoning, 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.1142354]
• 12: H. Bjorklund, W. Martens, T. Schwentick. Conjunctive query containment over trees. DBPL'07, pages 66--80.
• 13: Henrik Björklund , Wim Martens , Thomas Schwentick, Optimizing Conjunctive Queries over Trees Using Schema Information, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, August 25-29, 2008, Toruń, Poland [doi>10.1007/978-3-540-85238-4_10]
• 14: Laura Chiticariu , Wang-Chiew Tan, Debugging schema mappings with routes, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 15: Claire David, Complexity of Data Tree Patterns over XML Documents, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, August 25-29, 2008, Toruń, Poland [doi>10.1007/978-3-540-85238-4_22]
• 16: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 17: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Composing schema mappings: Second-order dependencies to the rescue, ACM Transactions on Database Systems (TODS), v.30 n.4, p.994-1055, December 2005 [doi>10.1145/1114244.1114249]
• 18: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Quasi-inverses of schema mappings, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-52, June 2008 [doi>10.1145/1366102.1366108]
• 19: Wenfei Fan , Philip Bohannon, Information preserving XML schema embedding, ACM Transactions on Database Systems (TODS), v.33 n.1, p.1-44, March 2008 [doi>10.1145/1331904.1331908]
• 20: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002 [doi>10.1145/567112.567117]
• 21: Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Journal of the ACM (JACM), v.53 n.2, p.238-272, March 2006 [doi>10.1145/1131342.1131345]
• 22: J. Hidders. Satisfiability of XPath expressions. In DBPL'03, pages 21--36.
• 23: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
• 24: Phokion G. Kolaitis , Jonathan Panttaja , Wang-Chiew Tan, The complexity of data exchange, 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.1142357]
• 25: Maurizio Lenzerini, Data integration: a theoretical perspective, 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.543644]
• 26: H. Lewis. Complexity results for classes of quantificational formulas. JCSS 21 (1980), 317--353.
• 27: Jayant Madhavan , Alon Y. Halevy, Composing mappings among data sources, Proceedings of the 29th international conference on Very large data bases, p.572-583, September 09-12, 2003, Berlin, Germany
• 28: Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching, Proceedings of the 18th International Conference on Data Engineering, p.117, February 26-March 01, 2002
• 29: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 30: Tova Milo , Sagit Zohar, Using Schema Matching to Simplify Heterogeneous Data Translation, Proceedings of the 24rd International Conference on Very Large Data Bases, p.122-133, August 24-27, 1998
• 31: Alan Nash , Philip A. Bernstein , Sergey Melnik, Composition of mappings given by embedded dependencies, ACM Transactions on Database Systems (TODS), v.32 n.1, p.4-es, March 2007 [doi>10.1145/1206049.1206053]
• 32: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China
• 33: L. Segoufin. Automata and logics for words and trees over an infinite alphabet. In CSL'06, pages 41--57.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases
          Subjects: Data translation**

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Algorithms, Languages, Theory

Keywords:
complexity, composition, consistency, mappings, schemas, xml