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)

[2]

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

[3]

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

[4]

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

[5]

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

[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

[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)

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[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

[18]

...

[19]

...

[20]

...

[21]

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

[22]

...

[23]

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

[24]

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

[25]

...

[26]

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

[27]

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

[28]

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

[29]

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

[30]

...

[31]

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

[32]

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

[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)

[34]

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

[35]

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

[36]

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

[37]

...

[38]

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

[39]

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

[40]

...

[41]

...

[42]

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

[43]

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

[44]

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