Composable XML integration grammars

ABSTRACT

The proliferation of XML as a standard for data representation and exchange in diverse, next-generation Web applications has created an emphatic need for effective XML data-integration tools. For several real-life scenarios, such XML data integration needs to be <i>DTD-directed</i> -- in other words, the target, integrated XML database must conform to a prespecified, user- or application-defined DTD. In this paper, we propose a novel formalism, <i>XML Integration Grammars (XIGs)</i>, for specifying DTD-directed integration of XML data. Abstractly, an XIG maps data from multiple XML sources to a target XML document that conforms to a predefined DTD. An XIG extracts source XML data via queries expressed in a fragment of XQuery, and controls target document generation with tree-valued attributes and the target DTD. The novelty of XIGs consists in not only their automatic support for DTD-conformance but also in their: an XIG may embed local and remote XIGs in its definition, and invoke these XIGs during its evaluation. This yields an important modularity property for our XIGs that allows one to divide a complex integration task into manageable sub-tasks and conquer each of them separately. To efficiently evaluate XIGs we provide algorithms for merging XML queries in an XIG and for scheduling queries and embedded XIGs. These lead to an effective framework, as well as a design tool for XQuery, for effectively specifying and computing complex, DTD-directed XML integration.

REFERENCES

• 1: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 2: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, XML with data values: typechecking revisited, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-149, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375570]
• 3: Chaitan Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu, XML-based information mediation with MIX, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.597-599, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Michael Benedikt , Chee-Yong Chan , Wenfei Fan , Juliana Freire , Rajeev Rastogi, Capturing both types and constraints in data integration, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872792]
• 5: M. Benedikt, C. Y. Chan, W. Fan, R. Rastogi, S. Zheng, and A. Zhou. DTD-directed publishing with attribute translation grammars. In VLDB, 2002.
• 6: P. Bohannon, S. Ganguly, H. Korth, P. Narayan, and P. Shenoy. Optimizing view queries in ROLEX to support navigable result trees. In VLDB, 2002.
• 7: Françoise Fabret, Dynamic Query Scheduling in Data Integration Systems, Proceedings of the 16th International Conference on Data Engineering, p.425, February 28-March 03, 2000
• 8: Luc Bouganim , Daniela Florescu , Patrick Valduriez, Dynamic Load Balancing in Hierarchical Parallel Database Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.436-447, September 03-06, 1996
• 9: T. Bray, J. Paoli, and C. M. Sperberg-McQueen. Extensible Markup Language (XML) 1.0. W3C Recommendation, Feb. 1998. http://www.w3.org/TR/REC-xml/.
• 10: M. J. Carey, D. Florescu, Z. G. Ives, Y. Lu, J. Shanmugasundaram, E. J. Shekita, and S. N. Subramanian. XPERANTO: Publishing object-relational data as XML. In WebDB, 2000.
• 11: D. Chamberlin et al. XQuery 1.0: An XML Query Language. W3C Working Draft, June 2001. http://www.w3.org/TR/xquery.
• 12: J. Clark. XSL Transformations (XSLT). W3C Recommendation, 1999. http://www.w3.org/TR/xslt.
• 13: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• 14: R. Farrow , T. J. Marlowe , D. M. Yellin, Composable attribute grammars: support for modularity in translator design and implementation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.223-234, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143210]
• 15: Mary Fernandez , Atsuyuki Morishima , Dan Suciu, Efficient evaluation of XML middle-ware queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.103-114, May 21-24, 2001, Santa Barbara, California, United States
• 16: Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey Ullman , Vasilis Vassalos , Jennifer Widom, The TSIMMIS Approach to Mediation: Data Models and Languages, Journal of Intelligent Information Systems, v.8 n.2, p.117-132, March/April 1997 [doi>10.1023/A:1008683107812]
• 17: Minos N. Garofalakis , Yannis E. Ioannidis, Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.296-305, August 25-29, 1997
• 18: Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301300]
• 19: R. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 17(2):416--429, 1969.
• 20: Waqar Hasan , Rajeev Motwani, Coloring Away Communication in Parallel Query Optimization, Proceedings of the 21th International Conference on Very Large Data Bases, p.239-250, September 11-15, 1995
• 21: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 22: Anthony Simon Kosky, Transforming databases with recursive data structures, University of Pennsylvania, Philadelphia, PA, 1996
• 23: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872793]
• 24: 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
• 25: L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating web data. In VLDB, 2002.
• 26: J. Shanmugasundaram et al. Relational databases for querying XML documents: Limitations and opportunities. VLDB Journal, pages 302--314, 1999.
• 27: S. Doaitse Swierstra , Harald Vogt, Higher Order Attribute Grammars, Proceedings on Attribute Grammars, Applications and Systems, p.256-296, June 04-13, 1991
• 28: H. Thompson et al. XML Schema. W3C Working Draft, May 2001. http://www.w3.org/XML/Schema.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Experimentation

Keywords:
XML, data integration, grammar