On wrapping query languages and efficient XML integration

ABSTRACT

Modern applications (Web portals, digital libraries, etc.) require integrated access to various information sources (from traditional DBMS to semistructured Web repositories), fast deployment and low maintenance cost in a rapidly evolving environment. Because of its flexibility, there is an increasing interest in using XML as a middleware model for such applications. XML enables fast wrapping and declarative integration. However, query processing in XML-based integration systems is still penalized by the lack of an algebra with adequate optimization properties and the difficulty to understand source query capabilities. In this paper, we propose an algebraic approach to support efficient XML query evaluation. We define a general purpose algebra suitable for semistructured on XML query languages. We show how this algebra can be used, with appropriate type information, to also wrap more structured query languages such as OQL or SQL. Finally, we develop new optimization techniques for XML-based integration systems.

REFERENCES

• 1: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The lorel query language for semistructured data. International Journal on Digital Libraries, 1(1)'68 88. Apr. 1997.
• 2: Sihem Amer-Yahia , Sophie Cluet , Claude Delobel, Bulk-Loading Techniques for Object Databases and an Application to Relational Data, Proceedings of the 24rd International Conference on Very Large Data Bases, p.534-545, August 24-27, 1998
• 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: Catriel Beeri , Tova Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, Proceeding of the 7th International Conference on Database Theory, p.296-313, January 10-12, 1999
• 5: C. Beeri and Y. Tzaban. SAL" An algebra for semistructured data and XML. In International Workshop on the Web and Databases (WebDB'99), Philadelphia, Pennsylvania, June 1999.
• 6: T. Bray, J. Paoli. and C. M. Sperberg-McQueen. Extensible markup language (XML) 1.0. W3C Recommendation. Feb. 1998. http"//www, w3.org/TR/REe-xml/.
• 7: Peter Buneman , Susan B. Davidson , Kyle Hart , G. Christian Overton , Limsoon Wong, A Data Transformation System for Biological Data Sources, Proceedings of the 21th International Conference on Very Large Data Bases, p.158-169, September 11-15, 1995
• 8: M. J. Carey , L. M. Haas , P. M. Schwarz , M. Arya , W. F. Cody , R. Fagin , M. Flickner , A. W. Luniewski , W. Niblack , D. Petkovic , J. Thomas , J. H. Williams , E. L. Wimmers, Towards heterogeneous multimedia information systems: the Garlic approach, Proceedings of the 5th International Workshop on Research Issues in Data Engineering-Distributed Object Management (RIDE-DOM'95), p.124, March 06-07, 1995
• 9: R. G. G. Cattell , Douglas K. Barry , Dirk Bartels , Mark Berler , Jeff Eastman , Sophie Gamerman , David Jordan , Adam Springer , Henry Strickland , Drew Wade, The object database standard: ODMG 2.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
• 11: V. Christophides , S. Abiteboul , S. Cluet , M. Scholl, From structured documents to novel query facilities, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.313-324, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: Vassilis Christophides , Sophie Cluet , Guido Moerkotte, Evaluating queries with generalized path expressions, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.413-422, June 04-06, 1996, Montreal, Quebec, Canada
• 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: Sophie Cluet , Guido Moerkotte, Nested Queries in Object Bases, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.226-242, August 30-September 01, 1993
• 15: S. Cluet and G. Moerkotte. Query processing in the schemaless and semistructured context, unpublished, 1996.
• 16: A. Deutsch. M. F. Fernandez. D. Florescu. A. Y. Levy, and D. Suciu. XML-QL: A query language for XML. Submission to the World Wide Web Consortium. Aug. 1998. http"//www, w3. org/TR/NOTE-xml-ql/.
• 17: M. F. Fernandez. D. Florescu. A. Y. Levy, and D. Suciu. Warehousing and incremental evaluation for web site management. In Proceedings of 1_4i#mes Journges Bases de Donn&s Avancdes. Hammamet. Tunisie. Oct. 1998.
• 18: M. F. Fernandez. J. Sim(#on. D. Suciu. and P. Wadler. A data model and algebra for XML query. Communication to the W3C. Jan. 2000.
• 19: M. F. Fernandez. J. Simeon. and P. Wadler (editors). XML query languages: Experiences and exemplars. Communication to the W3C. Sept. 1999.
• 20: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• 21: Daniela Florescu , Alon Levy , Ioana Manolescu , Dan Suciu, Query optimization in the presence of limited access patterns, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.311-322, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 22: Georges Gardarin , Sofiane Gannouni , Béatrice Finance , Peter Fankhausera , Wolfgang Klas , Dominique Pastrea , Régis Legoff , Antonis Ramfos, IRO-DB: a distributed system federating object and relational databases, Object-oriented multidatabase systems: a solution for advanced applications, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 23: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 24: 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
• 25: O. Kapitskaia, A. Tomasic. and P. Valduriez. Dealing with discrepancies in wrapper functionality. In Acres des 13i#mes Journges Bases de Donn&s Avanc&s (BDA'97), pages 327-349. Grenoble. France. Sept. 1997.
• 26: L. Liu , C. Pu , Y. Lee, An adaptive approach to query mediation across heterogeneous information sources, Proceedings of the First IFCIS International Conference on Cooperative Information Systems, p.144, June 19-21, 1996
• 27: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 28: Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 29: Alain Michard , Vassilis Christophides , Michel Scholl , Mike Stapleton , Dale Sutcliffe , Anne-Marie Vercoustre, The Aquarelle resource discovery system, Computer Networks and ISDN Systems, v.30 n.13, p.1185-1200, Aug. 1, 1998 [doi>10.1016/S0169-7552(98)00007-5]
• 30: M. Tamer Ozsu , P. Valduriez, Principles of distributed database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 31: Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina, Object Fusion in Mediator Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.413-424, September 03-06, 1996
• 32: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 33: Yannis Papakonstantinou , Ashish Gupta , Hector Garcia-Molina , Jeffrey D. Ullman, A Query Translation Scheme for Rapid Implementation of Wrappers, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.161-186, December 04-07, 1995
• 34: U. Pfeifer. free WAIS-sf. University of Dortmund. 0.5 edition. Oct. 1995.
• 35: J. Robie. J. Lapp, and D. Schach. XML query language (XQL). Workshop on XML Query Languages, Dec. 1998. W3C.
• 36: J. Sim(#on. Intggration de sources de donndes hgtdrog#nes (Ou comment rnarier sirnplicitd et efficacitg). PhD thesis. Universitd de Paris XI. Jan. 1999.
• 37: J. Simeon and S. Cluet. Design issues in XML languages: A unifying perspective. Draft manuscript, Oct. 1999.
• 38: H. S. Thompson, D. Beech. M. Maloney. and N. Mendelsohn. XML schema parts 1: Structures. W3C Working Draft. Sept. 1999.
• 39: Scaling heterogeneous databases and the design of Disco, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.449, May 27-30, 1996
• 40: Ling-Ling Yan , M. Tamer Özsu , Ling Liu, Accessing Heterogeneous Data Through Homogenization and Integration Mediators, Proceedings of the Second IFCIS International Conference on Cooperative Information Systems, p.130-139, June 24-27, 1997
• 41: CORPORATE National Information Standards Organization Staff, Information Retrieval: Application Service Definition and Protocol Specification, Z39.50-1995, NISO Press, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Experimentation, Languages