Query Containment for Data Integration Systems Todd D. Millstein, Alon Y. Levy, and Marc Friedman   View Paper (PDF)   Return to Views / Query Containment Abstract The problem of query containment is fundamental to many aspects of database systems, including query optimization, determining independence of queries from updates, and rewriting queries using views. In the data integration framework, however, the standard notion of query containment does not suffice. We define relative containment, which formalizes the notion of query containment relative to the sources available to the integration system. First we provide optimal bounds for relative containment for several important classes of datalog queries, including the common case of conjunctive queries. Next we provide bounds for the case when sources enforce access restrictions in the form of binding pattern constraints. Surprisingly, we show that relative containment for conjunctive queries is still decidable in this case, even though it is known that finding all answers to such queries may require a recursive datalog program over the sources. Finally, we provide tight bounds for variants of relative containment when the queries and source descriptions may contain comparison predicates. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Oliver M. Duschka : Complexity of Answering Queries Using Materialized Views. PODS 1998 : 254-263 [2] Sibel Adali , K. Selçuk Candan , Yannis Papakonstantinou , V. S. Subrahmanian : Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conf. 1996 : 137-148 [3] Alfred V. Aho , Yehoshua Sagiv , Jeffrey D. Ullman : Equivalences Among Relational Expressions. SIAM J. Comput. 8(2) : 218-246(1979) [4] José Luis Ambite , Naveen Ashish , Greg Barish , Craig A. Knoblock , Steven Minton , Pragnesh J. Modi , Ion Muslea , Andrew Philpot , Sheila Tejada : ARIADNE: A System for Constructing Mediators for Internet Sources. SIGMOD Conference 1998 : 561-563 [5] Catriel Beeri , Gershon Elber , Tova Milo , Yehoshua Sagiv , Oded Shmueli , Naftali Tishby , Yakov A. Kogan , David Konopnicki , Pini Mogilevski , Noam Slonim : WebSuite: A Tool Suite for Harnessing Web Data. WebDB 1998 : 152-171 [6] Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset : Rewriting Queries Using Views in Description Logics. PODS 1997 : 99-108 [7] Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini : Answering Queries Using Views in Description Logics. KRDB 1999 : 6-10 [8] Tiziana Catarci , Maurizio Lenzerini : Interschema Knowledge in Cooperative Information Systems. CoopIS 1993 : 55-62 [9] Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90 [10] Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200 [11] Surajit Chaudhuri , Moshe Y. Vardi : On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992 : 55-66 [12] Chung-Min Chen , Nick Roussopoulos : The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994 : 323-336 [13] William W. Cohen : Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity. SIGMOD Conference 1998 : 201-212 [14] Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan : Semantic Data Caching and Replacement. VLDB 1996 : 330-341 [15] Oliver M. Duschka , Michael R. Genesereth , Alon Y. Levy : Recursive Query Plans for Data Integration. JLP 43(1) : 49-73(2000) [16] Oliver M. Duschka , Michael R. Genesereth : Answering Recursive Queries Using Views. PODS 1997 : 109-116 [17] Oliver M. Duschka , Michael R. Genesereth : Query Planning in Infomaster. SAC 1997 : 0- [18] Daniela Florescu , Louiqa Raschid , Patrick Valduriez : A Methodology for Query Reformulation in CIS Using Semantic Knowledge. IJCIS 5(4) : 431-468(1996) [19] Marc Friedman , Alon Y. Levy , Todd D. Millstein : Navigational Plans For Data Integration. AAAI/IAAI 1999 : 67-73 [20] Marc Friedman , Daniel S. Weld : Efficiently Executing Information-Gathering Plans. IJCAI (1) 1997 : 785-791 [21] ... [22] Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Vasilis Vassalos , Jennifer Widom : The TSIMMIS Approach to Mediation: Data Models and Languages. JIIS 8(2) : 117-132(1997) [23] Gösta Grahne , Alberto O. Mendelzon : Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999 : 332-347 [24] Ashid Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom : Constraint Checking with Partial Information. PODS 1994 : 45-55 [25] Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang : Optimizing Queries Across Diverse Data Sources. VLDB 1997 : 276-285 [26] 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 [27] Arthur M. Keller , Julie Basu : A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB Journal 5(1) : 35-47(1996) [28] Anthony C. Klug : On Conjunctive Queries Containing Inequalities. JACM 35(1) : 146-160(1988) [29] Chung T. Kwok , Daniel S. Weld : Planning to Gather Information. AAAI/IAAI, Vol. 1 1996 : 32-39 [30] Eric Lambrecht , Subbarao Kambhampati , Senthil Gnanaprakasam : Optimizing Recursive Information-Gathering Plans. IJCAI 1999 : 1204-1211 [31] Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104 [32] Alon Y. Levy , Anand Rajaraman , Joann J. Ordille : Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996 : 251-262 [33] Alon Y. Levy , Yehoshua Sagiv : Queries Independent of Updates. VLDB 1993 : 171-181 [34] Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112 [35] Yehoshua Sagiv , Mihalis Yannakakis : Equivalences Among Relational Expressions with the Union and Difference Operators. JACM 27(4) : 633-655(1980) [36] Oded Shmueli : Equivalence of DATALOG Queries is Undecidable. JLP 15(3) : 231-241(1993) [37] Larry J. Stockmeyer : The Polynomial-Time Hierarchy. TCS 3(1) : 1-22(1976) [38] Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal 5(2) : 101-118(1996) [39] Ron van der Meyden : The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992 : 331-345 [40] H. Z. Yang , Per-Åke Larson : Query Transformation for PSJ-Queries. VLDB 1987 : 245-254 BIBTEX @inproceedings{DBLP:conf/pods/MillsteinLF00,   author    = {Todd D. Millstein and                 Alon Y. Levy and                 Marc Friedman},    title     = {Query Containment for Data Integration Systems},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {67-75},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.