Capturing both types and constraints in data integration

ABSTRACT

We propose a framework for integrating data from multiple relational sources into an XML document that both conforms to a given DTD and satisfies predefined XML constraints. The framework is based on a specification language, AIG, that extends a DTD by (1) associating element types with semantic attributes (inherited and synthesized, inspired by the corresponding notions from Attribute Grammars), (2) computing these attributes via parameterized SQL queries over multiple data sources, and (3) incorporating XML keys and inclusion constraints. The novelty of AIG consists in semantic attributes and their dependency relations for controlling context-dependent, DTD-directed construction of XML documents, as well as for checking XML constraints in parallel with document-generation. We also present cost-based optimization techniques for efficiently evaluating AIGs, including algorithms for merging queries and for scheduling queries on multiple data sources. This provides a new grammar-based approach for data integration under both syntactic and semantic constraints.

REFERENCES

• 1: Marcelo Arenas , Wenfei Fan , Leonid Libkin, On verifying consistency of XML specifications, 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.543647]
• 2: 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
• 3: M. Benedikt, C. Y. Chan, W. Fan, R. Rastogi, S. Zheng, and A. Zhou. DTD-directed publishing with attribute translation grammars. In VLDB, 2002.
• 4: 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/.
• 5: 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.
• 6: R. G. G. Cattell , Douglas K. Barry , Mark Berler , Jeff Eastman , David Jordan , Craig Russell , Olaf Schadow , Torsten Stanienda , Fernando Velez, The object data standard: ODMG 3.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 7: D. Chamberlin et al. XQuery 1.0: An XML Query Language. W3C Working Draft, June 2001. http://www.w3.org/TR/xquery.
• 8: B. Choi. What are real DTDs like. In WebDB, 2002.
• 9: J. Clark. XSL Transformations (XSLT). W3C Recommendation, Nov. 1999. http://www.w3.org/TR/xslt.
• 10: 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
• 11: H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Ligiez, S. Tison, and M. Tommasa. Tree Automata Techniques and Applications. Online, 1999.
• 12: Susan B. Davidson , Anthony Kosky, WOL: A Language for Database Transformations and Constraints, Proceedings of the Thirteenth International Conference on Data Engineering, p.55-65, April 07-11, 1997
• 13: P. Deransart, M. Jourdan, and B. Lorho (eds). Attribute Grammars. LNCS 323, 1988.
• 14: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang, Optimizing Queries Across Diverse Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.276-285, August 25-29, 1997
• 18: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 19: 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]
• 20: 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
• 21: Frank Neven , Jan Van Den Bussche, Expressiveness of structured document query languages based on attribute grammars, Journal of the ACM (JACM), v.49 n.1, p.56-100, January 2002 [doi>10.1145/505241.505245]
• 22: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 23: L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating web data. In VLDB, 2002.
• 24: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 25: V. Rayward-Smith, F. Burton, and G.J.Janacek. Scheduling Parallel Programs Assuming Preallocation. In P. Chretienne, E. Coffman, J. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, pages 145--165. John Wiley & Sons, 1995.
• 26: Jayavel Shanmugasundaram , Jerry Kiernan , Eugene J. Shekita , Catalina Fan , John Funderburk, Querying XML Views of Relational Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.261-270, September 11-14, 2001
• 27: Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr , Michael Carey , Bruce Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently publishing relational data as XML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.133-154, September 2001
• 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.1 Logical Design
          Subjects: Data models

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

          Nouns: XML

General Terms:
Design, Languages, Theory