Digital Symposium Collection 2000

Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources Chen-Chuan K. Chang and Hector Garcia-Molina   View Paper (PDF)   Return to New Data Types Note: The quality of the PDF contained herein reflects that of the material supplied to the DiSC'00 Production Team. Abstract In this paper we present a mechanism for translating constraint queries, i.e., Boolean expressions of constraints, across heterogeneous information sources. Integrating such systems is difficult in part because they use a wide range of constraints as the vocabulary for formulating queries. We describe algorithms that apply user-provided mapping rules to translate query constraints into ones that are understood and supported in another context, e.g.,that use the proper operators and value formats. We show that the translated queries minimally subsume the original ones. Furthermore, the translated queries are also the most compact possible. Unlike other query mapping work, we effectively consider inter-dependencies among constraints, i.e., we handle constraints that cannot be translated independently. Furthermore, when constraints are not fully supported, our framework explores relaxations (semantic rewritings) into the closest supported version. Our most sophisticated algorithm (Algorithm TDQM) does not blindly convert queries to DNF (which would be easier to translate, but expensive); instead it performs a top-down mapping of a query tree, and does local query structure conversion only when necessary. References Note: References link to DBLP on the Web. [1] Gio Wiederhold : Mediators in the Architecture of Future Information Systems. IEEE Computer 25(3) : 38-49(1992) [2] Jeffrey D. Ullman : Information Integration Using Logical Views. ICDT 1997 : 19-40 [3] Alon Y. Levy , Anand Rajaraman , Joann J. Ordille : Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996 : 251-262 [4] Alon Y. Levy , Anand Rajaraman , Joann J. Ordille : Query-Answering Algorithms for Information Agents. AAAI/IAAI, Vol. 1 1996 : 40-47 [5] Yannis Papakonstantinou , Hector Garcia-Molina , Jeffrey D. Ullman : MedMaker: A Mediation System Based on Declarative Specifications. ICDE 1996 : 132-141 [6] Yannis Papakonstantinou , Ashish Gupta , Hector Garcia-Molina , Jeffrey D. Ullman : A Query Translation Scheme for Rapid Implementation of Wrappers. DOOD 1995 : 161-186 [7] ... [8] Michael R. Genesereth , Arthur M. Keller , Oliver M. Duschka : Infomaster: An Information Integration System. SIGMOD Conference 1997 : 539-542 [9] Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang : Optimizing Queries Across Diverse Data Sources. VLDB 1997 : 276-285 [10] Mary Tork Roth , Peter M. Schwarz : Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources. VLDB 1997 : 266-275 [11] ... [12] Hector Garcia-Molina , Wilburt Labio , Ramana Yerneni : Capability-Sensitive Query Processing on Internet Sources. ICDE 1999 : 50-59 [13] Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112 [14] Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman : Answering Queries Using Limited External Processors. PODS 1996 : 227-237 [15] Chen-Chuan K. Chang , Hector Garcia-Molina , Andreas Paepcke : Boolean Query Mapping Across Heterogeneous Information Sources. TKDE 8(4) : 515-521(1996) [16] ... [17] ... [18] Sandra Heiler : Sematic Interoperability. Computing Surveys 27(2) : 271-273(1995) [19] Yannis Papakonstantinou , Ashish Gupta , Laura M. Haas : Capabilities-Based Query Rewriting in Mediator Systems. PDIS 1996 : 170-181 [20] Chen-Chuan K. Chang , Hector Garcia-Molina : Conjunctive Constraint Mapping for Data Translation. ACM DL 1998 : 49-58 [21] Chen-Chuan K. Chang , Hector Garcia-Molina , Andreas Paepcke : Predicate Rewriting for Translating Boolean Queries in a Heterogeneous Information System. TOIS 17(1) : 1-39(1999) [22] Alfred V. Aho , John E. Hopcroft , Jeffrey D. Ullman : The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6 [23] ... BIBTEX @inproceedings{DBLP:conf/sigmod/ChangG99,   author    = {Chen-Chuan K. Chang and                 Hector Garcia-Molina},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Mind Your Vocabulary: Query Mapping Across Heterogeneous Information                 Sources},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {335-346},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM