Deciding Containment for Queries with Complex Objects.

@inproceedings{DBLP:conf/pods/LevyS97,
  author    = {Alon Y. Levy and
               Dan Suciu},
  title     = {Deciding Containment for Queries with Complex Objects},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {20-31},
  ee        = {http://doi.acm.org/10.1145/263661.263665, db/conf/pods/LevyS97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We address the problem of query containment and query equivalence for complex objects. We show that for a certain conjunctive query language for complex objects, query containment and weak query equivalence are decidable. Our results also have two important consequences. First, when the answer of the two queries are guaranteed not to contain empty sets, then weak equivalence coincides with equivalence, and our result answers partially an open problem about the equivalence of nest, unnest queries for complex objects [24]. Second, we show that checking the equivalence of conjunctive queries with grouping and aggregates is NP-complete.

Our results rely on a translation of the containment and equivalence conditions for complex objects into novel conditions on conjunctive queries, which we call simulation and strong simulation respectively. These conditions are more complex than containment of conjunctive queries, because they involve arbitrary numbers of quantifier alternations. We show that checking simulation and strong simulation for conjunctive queries is NP-complete.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[2]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[3]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[4]

Nicole Bidoit: The Verso Algebra or How to Answer Queries with Fewer Joins. J. Comput. Syst. Sci. 35(3): 321-364(1987) BibTeX

[5]

Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350 BibTeX

[6]

Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516 BibTeX

[7]

Peter Buneman, Shamim A. Naqvi, Val Tannen, Limsoon Wong: Principles of Programming with Complex Objects and Collection Types. Theor. Comput. Sci. 149(1): 3-48(1995) BibTeX

[8]

Peter Buneman, Achim Jung, Atsushi Ohori: Using Powerdomains to Generalize Relational Databases. Theor. Comput. Sci. 91(1): 23-55(1991) BibTeX

[9]

R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
BibTeX

[10]

Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211 BibTeX

[11]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[12]

Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX

[13]

Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366 BibTeX

[14]

Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 BibTeX

[15]

Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70 BibTeX

[16]

...

[17]

Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX

[18]

...

[19]

...

[20]

...

[21]

Dirk Van Gucht, Patrick C. Fischer: Multilevel Nested Relational Structures. J. Comput. Syst. Sci. 36(1): 77-105(1988) BibTeX

[22]

...

[23]

Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55 BibTeX

[24]

Marc Gyssens, Jan Paredaens, Dirk Van Gucht: On a Hierarchy of Classes for Nested Databases. Inf. Process. Lett. 36(5): 259-266(1990) BibTeX

[25]

...

[26]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[27]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX

[28]

Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534 BibTeX

[29]

Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107 BibTeX

[30]

...

[31]

Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 BibTeX

[32]

Leonid Libkin, Limsoon Wong: Semantic Representations and Query Languages for Or-sets. PODS 1993: 37-48 BibTeX

[33]

Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX

[34]

Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX

[35]

Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Foundations of Aggregation Constraints. PPCP 1994: 193-204 BibTeX

[36]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[37]

...

[38]

Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 15(3): 231-241(1993) BibTeX

[39]

Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281 BibTeX

[40]

...

[41]

...

[42]

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 BibTeX

[43]

Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

[44]

Xubo Zhang, Z. Meral Özsoyoglu: On Efficient Reasoning with Implication Constraints. DOOD 1993: 236-252 BibTeX

Referenced by

1. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
2. Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57
3. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
4. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158
5. Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263