Optimizing Queries Across Diverse Data Sources.

Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
  author    = {Laura M. Haas and
               Donald Kossmann and
               Edward L. Wimmers and
               Jun Yang},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Optimizing Queries Across Diverse Data Sources},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {276-285},
  ee        = {db/conf/vldb/HaasKWY97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP,}


Businesses today need to interrelate data stored in diverse systems with differing capabilities, ideally via a single high-level query interface. We present the design of a query optimizer for Garlic[C+95], a middleware system designed to integrate data from a broad range of data sources with very different query capabilities. Garlic's optimizer extends the rule-based approach of [Loh88] to work in a heterogeneous environment, by defining generic rules for the middleware and using wrapper-provided rules to encapsulate the capabilities of each data source. This approach offers great advantages in terms of plan quality, extensibility to new sources, incremental implementation of rules for new sources, and the ability to express the capabilities of a diverse set of sources. We describe the design and implementation of this optimizer, and illustrate its actions through an example.

Copyright © 1997 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents BibTeX

Electronic Edition

From CS Dept., University Trier (Germany)


The Garlic Home Page:


Michael J. Carey, Laura M. Haas, Peter M. Schwarz, Manish Arya, William F. Cody, Ronald Fagin, Myron Flickner, Allen Luniewski, Wayne Niblack, Dragutin Petkovic, Joachim Thomas II, John H. Williams, Edward L. Wimmers: Towards Heterogeneous Multimedia Information Systems: The Garlic Approach. RIDE-DOM 1995: 124-131 BibTeX
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542 BibTeX
Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353 BibTeX
Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan: Query Optimization in a Heterogeneous DBMS. VLDB 1992: 277-291 BibTeX
Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160 BibTeX
Daniela Florescu, Louiqa Raschid, Patrick Valduriez: Using Heterogeneous Equivalences for Query Rewriting in Multidatabase Systems. CoopIS 1995: 158-169 BibTeX
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
Peter Gassner, Guy M. Lohman, K. Bernhard Schiefer, Yun Wang: Query Optimization in the IBM DB2 Family. IEEE Data Eng. Bull. 16(4): 4-18(1993) BibTeX
Georges Gardarin, Fei Sha, Zhao-Hui Tang: Calibrating the Query Optimizer Cost Model of IRO-DB, an Object-Oriented Federated Database System. VLDB 1996: 378-389 BibTeX
Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 BibTeX
Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229 BibTeX
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 BibTeX
Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX
William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121 BibTeX
Wayne Niblack, Ron Barber, William Equitz, Myron Flickner, Eduardo H. Glasman, Dragutin Petkovic, Peter Yanker, Christos Faloutsos, Gabriel Taubin: The QBIC Project: Querying Images by Content, Using Color, Texture, and Shape. Storage and Retrieval for Image and Video Databases (SPIE) 1993: 173-187 BibTeX
Yannis Papakonstantinou, Ashish Gupta, Laura M. Haas: Capabilities-Based Query Rewriting in Mediator Systems. PDIS 1996: 170-181 BibTeX
Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 BibTeX
Xiaolei Qian: Query Folding. ICDE 1996: 48-55 BibTeX
Mary Tork Roth, Peter M. Schwarz: Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources. VLDB 1997: 266-275 BibTeX
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
Ming-Chien Shan, Rafi Ahmed, Jim Davis, Weimin Du, William Kent: Pegasus: A Heterogeneous Information Management System. Modern Database Systems 1995: 664-682 BibTeX
Gio Wiederhold: Intelligent Integration of Information. SIGMOD Conference 1993: 434-437 BibTeX

Referenced by

  1. Manuel Rodriguez-Martinez, Nick Roussopoulos: MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources. SIGMOD Conference 2000: 213-224
  2. Ron Avnur, Joseph M. Hellerstein: Eddies: Continuously Adaptive Query Processing. SIGMOD Conference 2000: 261-272
  3. Roy Goldman, Jennifer Widom: WSQ/DSQ: A Practical Approach for Combined Querying of Databases and the Web. SIGMOD Conference 2000: 285-296
  4. Vassilis Christophides, Sophie Cluet, Jérôme Siméon: On Wrapping Query Languages and Efficient XML Integration. SIGMOD Conference 2000: 141-152
  5. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
  6. Mary Tork Roth, Fatma Ozcan, Laura M. Haas: Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System. VLDB 1999: 599-610
  7. Vanja Josifovski, Tore Risch: Integrating Heterogenous Overlapping Databases through Object-Oriented Transformations. VLDB 1999: 435-446
  8. Laura M. Haas, Donald Kossmann, Ioana Ursu: Loading a Cache with Query Results. VLDB 1999: 351-362
  9. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
  10. Zachary G. Ives, Daniela Florescu, Marc Friedman, Alon Y. Levy, Daniel S. Weld: An Adaptive Query Execution System for Data Integration. SIGMOD Conference 1999: 299-310
  11. Daniela Florescu, Alon Y. Levy, Ioana Manolescu, Dan Suciu: Query Optimization in the Presence of Limited Access Patterns. SIGMOD Conference 1999: 311-322
  12. Kevin Chen-Chuan Chang, Hector Garcia-Molina: Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources. SIGMOD Conference 1999: 335-346
  13. Reinhard Braumandl, Alfons Kemper, Donald Kossmann: Database Patchwork on the Internet. SIGMOD Conference 1999: 550-552
  14. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
  15. Uwe Röhm, Klemens Böhm: Working Together in Harmony - An Implementation of the CORBA Object Query Service and Its Evaluation. ICDE 1999: 238-247
  16. Ling Liu: Query Routing in Large-Scale Digital Library Systems. ICDE 1999: 154-163
  17. Hector Garcia-Molina, Wilburt Labio, Ramana Yerneni: Capability-Sensitive Query Processing on Internet Sources. ICDE 1999: 50-59
  18. Peter McBrien, Alexandra Poulovassilis: Automatic Migration and Wrapping of Database Applications - A Schema Transformation Approach. ER 1999: 96-113
  19. Vladimir Zadorozhny: Cost-based Magic for Web Queries (Extended Abstract). ADBIS (Short Papers) 1999: 185-192
  20. Anthony Tomasic, Louiqa Raschid, Patrick Valduriez: Scaling Access to Heterogeneous Data Sources with DISCO. IEEE Trans. Knowl. Data Eng. 10(5): 808-823(1998)
  21. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
  22. Luis Gravano, Yannis Papakonstantinou: Mediating and Metasearching on the Internet. IEEE Data Eng. Bull. 21(2): 28-36(1998)
  23. Michael J. Carey, Laura M. Haas, Jim Kleewein, Berthold Reinwald: Data Access Interoperability in the IBM Database Family. IEEE Data Eng. Bull. 21(3): 4-11(1998)
  24. Shivakumar Venkataraman, Tian Zhang: Heterogeneous Database Query Optimization in DB2 Universal DataJoiner. VLDB 1998: 685-689
  25. Clara Nippl, Bernhard Mitschang: TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer. VLDB 1998: 251-262
  26. Frédéric Gingras, Laks V. S. Lakshmanan: nD-SQL: A Multi-Dimensional Language for Interoperability and OLAP. VLDB 1998: 134-145
  27. Subbu N. Subramanian, Shivakumar Venkataraman: Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998: 319-330
  28. Chen Li, Ramana Yerneni, Vasilis Vassalos, Hector Garcia-Molina, Yannis Papakonstantinou, Jeffrey D. Ullman, Murty Valiveti: Capability Based Mediation in TSIMMIS. SIGMOD Conference 1998: 564-566
  29. Michael Jaedicke, Bernhard Mitschang: On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS. SIGMOD Conference 1998: 379-389
  30. Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998: 414-425
  31. Ramana Yerneni, Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Fusion Queries over Internet Databases. EDBT 1998: 57-71
  32. George A. Mihaila, Louiqa Raschid, Anthony Tomasic: Equal Time for Data on the Internet with WebSemantics. EDBT 1998: 87-101
  33. Fatma Ozcan, Sena Nural, Pinar Koksal, Cem Evrendilek, Asuman Dogac: Dynamic Query Optimization in Multidatabases. IEEE Data Eng. Bull. 20(3): 38-45(1997)
  34. Ling Liu, Calton Pu: Dynamic Query Processing in DIOM. IEEE Data Eng. Bull. 20(3): 30-37(1997)
  35. Vasilis Vassalos, Yannis Papakonstantinou: Describing and Using Query Capabilities of Heterogeneous Sources. VLDB 1997: 256-265
  36. Mary Tork Roth, Peter M. Schwarz: Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources. VLDB 1997: 266-275
  37. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: An Optimizer for Heterogeneous Systems with NonStandard Data and Search Capabilities. IEEE Data Eng. Bull. 19(4): 37-44(1996)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:16 2009