Querying Heterogeneous Information Sources Using Source Descriptions.

Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262
  author    = {Alon Y. Levy and
               Anand Rajaraman and
               Joann J. Ordille},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Querying Heterogeneous Information Sources Using Source Descriptions},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {251-262},
  ee        = {db/conf/vldb/LevyRO96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP,}


We witness a rapid increase in the number of structured information sources that are available online, especially on the WWW. These sources store interrelated data on topics such as product information, stock market information, entertainment, etc. We would like to use the data stored in these databases to answer complex queries that go beyond keyword searches. We describe the Information Manifold, an implemented system that provides uniform access to a heterogeneous collection of more than 100 information sources, on the WWW. IM contains declarative descriptions of the contents and capabilities of the information sources. We describe algorithms that use the source descriptions to prune efficiently the set of information sources for a given query and practical algorithms to generate executable query plans. We also present experimental studies that indicate that the architecture and algorithms used in the Information Manifold scale up well to several hundred information sources.

Copyright © 1996 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

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents BibTeX

Electronic Edition


Yigal Arens, Chin Y. Chee, Chun-Nan Hsu, Craig A. Knoblock: Retrieving and Integrating Data from Multiple Information Sources. Int. J. Cooperative Inf. Syst. 2(2): 127-158(1993) BibTeX
Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148 BibTeX
Christine Collet, Michael N. Huhns, Wei-Min Shen: Resource Integration Using a Large Knowledge Base in Carnot. IEEE Computer 24(12): 55-62(1991) BibTeX
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX
Oren Etzioni, Daniel S. Weld: A Softbot-Based Interface to the Internet. Commun. ACM 37(7): 72-76(1994) BibTeX
Daniela Florescu, Louiqa Raschid, Patrick Valduriez: Using Heterogeneous Equivalences for Query Rewriting in Multidatabase Systems. CoopIS 1995: 158-169 BibTeX
David Konopnicki, Oded Shmueli: W3QS: A Query System for the World-Wide Web. VLDB 1995: 54-65 BibTeX
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Query-Answering Algorithms for Information Agents. AAAI/IAAI, Vol. 1 1996: 40-47 BibTeX
Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX
Alon Y. Levy, Divesh Srivastava, Thomas Kirk: Data Model and Query Evaluation in Global Information Systems. J. Intell. Inf. Syst. 5(2): 121-143(1995) BibTeX
Katherine A. Morris: An Algorithm for Ordering Subgoals in NAIL! PODS 1988: 82-88 BibTeX
Joann J. Ordille, Barton P. Miller: Distributed Active Catalogs and Meta-Data Caching in Descriptive Name Services. ICDCS 1993: 120-129 BibTeX
Yannis Papakonstantinou, Ashish Gupta, Hector Garcia-Molina, Jeffrey D. Ullman: A Query Translation Scheme for Rapid Implementation of Wrappers. DOOD 1995: 161-186 BibTeX
Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112 BibTeX
Anand Rajaraman, Jeffrey D. Ullman: Integrating Information by Outerjoins and Full Disjunctions. PODS 1996: 238-248 BibTeX
Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. VLDB 1996: 318-329 BibTeX
H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 BibTeX

Referenced by

  1. Chen Li, Mayank Bawa, Jeffrey D. Ullman: Minimizing View Sets without Losing Query-Answering Power. ICDT 2001: 99-113
  2. Roy Goldman, Jennifer Widom: WSQ/DSQ: A Practical Approach for Combined Querying of Databases and the Web. SIGMOD Conference 2000: 285-296
  3. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
  4. Mengchi Liu, Tok Wang Ling: A Data Model for Semistructured Data with Partial and Inconsistent Information. EDBT 2000: 317-331
  5. Mike P. Papazoglou, Jeroen Hoppenbrouwers: Contextualizing the Information Space in Federated Digital Libraries. SIGMOD Record 28(1): 40-46(1999)
  6. Ruxandra Domenig, Klaus R. Dittrich: An Overview and Classification of Mediated Query Systems. SIGMOD Record 28(3): 63-72(1999)
  7. Sonia Bergamaschi, Silvana Castano, Maurizio Vincini: Semantic Integration of Semistructured and Structured Data Sources. SIGMOD Record 28(1): 54-59(1999)
  8. Serge Abiteboul, Sophie Cluet, Tova Milo, Pini Mogilevsky, Jérôme Siméon, Sagit Zohar: Tools for Data Translation and Integration. IEEE Data Eng. Bull. 22(1): 3-8(1999)
  9. Uwe Hohenstein, Andreas Ebert: Automatic Migration of Files into Relational Databases. Workshop on Web Information and Data Management 1999: 17-21
  10. Greg Barish, Dan DiPasquo, Craig A. Knoblock, Steven Minton: An Efficient Plan Execution System for Information Management Agents. Workshop on Web Information and Data Management 1999: 1-5
  11. 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
  12. Felix Naumann, Ulf Leser, Johann Christoph Freytag: Quality-driven Integration of Heterogenous Information Systems. VLDB 1999: 447-458
  13. Donko Donjerkovic, Raghu Ramakrishnan: Probabilistic Optimization of Top N Queries. VLDB 1999: 411-422
  14. Luc Bouganim, Tatiana Chan-Sine-Ying, Tuyet-Tram Dang-Ngoc, Jean-Luc Darroux, Georges Gardarin, Fei Sha: Miro Web: Integrating Multiple Data Sources through Semistructured Data Types. VLDB 1999: 750-753
  15. Ramana Yerneni, Chen Li, Hector Garcia-Molina, Jeffrey D. Ullman: Computing Capabilities of Mediators. SIGMOD Conference 1999: 443-454
  16. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
  17. 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
  18. Daniela Florescu, Alon Y. Levy, Ioana Manolescu, Dan Suciu: Query Optimization in the Presence of Limited Access Patterns. SIGMOD Conference 1999: 311-322
  19. Hasan Davulcu, Juliana Freire, Michael Kifer, I. V. Ramakrishnan: A Layered Architecture for Querying Dynamic Web Content. SIGMOD Conference 1999: 491-502
  20. Kevin Chen-Chuan Chang, Hector Garcia-Molina: Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources. SIGMOD Conference 1999: 335-346
  21. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
  22. Gösta Grahne, Alberto O. Mendelzon: Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999: 332-347
  23. Catriel Beeri, Tova Milo: Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999: 296-313
  24. Yannis Papakonstantinou, Pavel Velikhov: Enhancing Semistructured Data Mediators with Document Type Definitions. ICDE 1999: 136-145
  25. Marian H. Nodine, William Bohrer, Anne H. H. Ngu: Semantic Brokering over Dynamic Heterogeneous Data Sources in InfoSleuth. ICDE 1999: 358-365
  26. Ling Liu: Query Routing in Large-Scale Digital Library Systems. ICDE 1999: 154-163
  27. Hector Garcia-Molina, Wilburt Labio, Ramana Yerneni: Capability-Sensitive Query Processing on Internet Sources. ICDE 1999: 50-59
  28. Xun Cheng, Guozhu Dong, Tzekwan Lau, Jianwen Su: Data Integration by Describing Sources with Constraint Databases. ICDE 1999: 374-381
  29. Athman Bouguettaya, Boualem Benatallah, Mourad Ouzzani, Lily Hendra: Using Java and CORBA for Implementing Internet Databases. ICDE 1999: 218-227
  30. Bertram Ludäscher, Amarnath Gupta: Modeling Interactive Web Sources for Information Mediation. ER (Workshops) 1999: 225-238
  31. Zoubida Kedad, Elisabeth Métais: Dealing with Semantic Heterogeneity During Data Integration. ER 1999: 325-339
  32. Silvana Castano, Valeria De Antonellis: Building Views over Semistructured Data Sources. ER 1999: 146-160
  33. Praveen Seshadri: Enhanced Abstract Data Types in Object-Relational Databases. VLDB J. 7(3): 130-140(1998)
  34. Anthony Tomasic, Louiqa Raschid, Patrick Valduriez: Scaling Access to Heterogeneous Data Sources with DISCO. IEEE Trans. Knowl. Data Eng. 10(5): 808-823(1998)
  35. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
  36. Udi Manber, Peter A. Bigot: Connecting Diverse Web Search Facilities. IEEE Data Eng. Bull. 21(2): 21-27(1998)
  37. Luis Gravano, Yannis Papakonstantinou: Mediating and Metasearching on the Internet. IEEE Data Eng. Bull. 21(2): 28-36(1998)
  38. Tova Milo, Sagit Zohar: Using Schema Matching to Simplify Heterogeneous Data Translation. VLDB 1998: 122-133
  39. Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon: DTL's DataSpot: Database Exploration Using Plain Language. VLDB 1998: 645-649
  40. Subbu N. Subramanian, Shivakumar Venkataraman: Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998: 319-330
  41. Renée J. Miller: Using Schematically Heterogeneous Structures. SIGMOD Conference 1998: 189-200
  42. 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
  43. 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
  44. Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon: DTL's DataSpot: Database Exploration as Easy as Browsing the Web ... SIGMOD Conference 1998: 590-592
  45. William W. Cohen: Providing Database-like Access to the Web Using Queries Based on Textual Similarity. SIGMOD Conference 1998: 558-560
  46. William W. Cohen: Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity. SIGMOD Conference 1998: 201-212
  47. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
  48. Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263
  49. Laks V. S. Lakshmanan, Subbu N. Subramanian, Nita Goyal, Ravi Krishnamurthy: On Query Spreadsheets. ICDE 1998: 134-141
  50. Jarek Gryz: Query Folding with Inclusion Dependencies. ICDE 1998: 126-133
  51. Ramana Yerneni, Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Fusion Queries over Internet Databases. EDBT 1998: 57-71
  52. Vasilis Vassalos, Yannis Papakonstantinou: Describing and Using Query Capabilities of Heterogeneous Sources. VLDB 1997: 256-265
  53. Mary Tork Roth, Peter M. Schwarz: Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources. VLDB 1997: 266-275
  54. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
  55. Daniela Florescu, Daphne Koller, Alon Y. Levy: Using Probabilistic Information in Data Integration. VLDB 1997: 216-225
  56. Paolo Atzeni, Giansalvatore Mecca, Paolo Merialdo: To Weave the Web. VLDB 1997: 206-215
  57. Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: STRUDEL: A Web-site Management System. SIGMOD Conference 1997: 549-552
  58. Roberto J. Bayardo Jr., William Bohrer, Richard S. Brice, Andrzej Cichocki, Jerry Fowler, Abdelsalam Helal, Vipul Kashyap, Tomasz Ksiezyk, Gale Martin, Marian H. Nodine, Mosfeq Rashid, Marek Rusinkiewicz, Ray Shea, C. Unnikrishnan, Amy Unruh, Darrell Woelk: InfoSleuth: Semantic Integration of Information in Open and Dynamic Environments (Experience Paper). SIGMOD Conference 1997: 195-206
  59. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
  60. Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116
  61. Catriel Beeri, Alon Y. Levy, Marie-Christine Rousset: Rewriting Queries Using Views in Description Logics. PODS 1997: 99-108
  62. Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40
  63. Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70
  64. Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18
  65. Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. VLDB 1996: 318-329
  66. Alon Y. Levy: Obtaining Complete Answers from Incomplete Databases. VLDB 1996: 402-412
  67. Anand Rajaraman, Jeffrey D. Ullman: Integrating Information by Outerjoins and Full Disjunctions. PODS 1996: 238-248
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:11 2009