Containment of Conjunctive Queries: Beyond Relations as Sets.

@article{DBLP:journals/tods/IoannidisR95,
  author    = {Yannis E. Ioannidis and
               Raghu Ramakrishnan},
  title     = {Containment of Conjunctive Queries: Beyond Relations as Sets},
  journal   = {ACM Trans. Database Syst.},
  volume    = {20},
  number    = {3},
  year      = {1995},
  pages     = {288-324},
  ee        = {http://doi.acm.org/10.1145/211414.211419, db/journals/tods/IoannidisR95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Conjunctive queries are queries over a relational database and are at the core of relational query languages such as SQL. Testing for containment (and equivalence) of such queries arises as part of many advanced features of query optimization, for example, using materialized views, processing correlated nested queries, semantic query optimization, and global query optimization. Earlier formal work on the topic has examined conjunctive queries over sets of tuples, where each query can be viewed as a function from sets to sets. Containment (and equivalence) of conjunctive queries has been naturally defined based on set incluslon and has been shown to be an NP-complete problem.

Even in SQL, however, queries over multisets of tuples may be posed. In fact, relations are treated as multisets by default, with duplicates being eliminated only after explicit requests. Thus, in order to reason about containment/equivalence of a large class of SQL queries, it is necessary to consider a generalization of conjunctive queries, in which relations are interpreted as multisets of tuples: The view of a relation as a set of tuples must be generalized.

In this paper we study conjunctive queries over databases in which each tuple has an associated label. This generalized notion of a database allows us to consider relations that are multisets and relations that are fuzzy sets. As a special case, we can also model traditional set-relations by making the label associated with a tuple be either "true" (meaning that the tuple is in the relation) or "false" (meaning that the tuple is not in the relation). In order to keep our results general, we consider a variety of label systems, where each label system is essentially a set of conditions on the labels that can be associated with tuples. Once a result is established for a label system, it holds for all interpretations of relations that satisfy these conditions. For example, we present a necessary and sufficient condition for containment of conjunctive queries for label systems of a type that abstracts both the traditional set-relations and fuzzy sets. We also present a different necessary and sufficient condition for containment of a restricted class of conjunctive queries for a label system that abstracts relations as multisets. Finally, we show that containment of unions of conjunctive queries is decidable for label systems of the first type and undecidable for label systems of the second type. This result underscores the fundamental difference between viewing relations as sets and as multisets, and motivates a closer examination of relations as multisets, given their importance in SQL.

Copyright © 1995 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[Aho et al. 1979]

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

[Blakeley et al. 1986]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX

[Chandra and Merlin 1977]

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

[Chaudhuri and Vardi 1993]

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

[Chaudhuri et al. 1995]

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

[Davis 1982]

...

[Dayal et al. 1982]

Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123 BibTeX

[Graefe 1995]

...

[Grant and Minker 1981]

John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX

[Ioannidis and Wong 1991]

Yannis E. Ioannidis, Eugene Wong: Towards an Algebraic Theory of Recursion. J. ACM 38(2): 329-381(1991) BibTeX

[Johnson and Klug 1982]

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169 BibTeX

[King 1981]

Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX

[Maher and Ramakrishnan 1989]

Michael J. Maher, Raghu Ramakrishnan: Déjà Vu in Fixpoints of Logic Programs. NACLP 1989: 963-980 BibTeX

[Mumick et al. 1990]

Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX

[Negri et al. 1991]

Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991) BibTeX

[Paysaye and Chignell 1988]

...

[Sagiv and Yannakakis 1980]

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

[Sellis 1986]

Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX

[Shenoy and Özsoyoglu 1987]

Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195 BibTeX

[Tsatalos et al. 1994]

Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378 BibTeX

[van Emden 1986]

Maarten H. van Emden: Quantitative Deduction and its Fixpoint Theory. J. Log. Program. 3(1): 37-53(1986) BibTeX

[Zadeh 1965]

Lotfi A. Zadeh: Fuzzy Sets. Information and Control 8(3): 338-353(1965) BibTeX

Referenced by

1. Sara Cohen, Werner Nutt, Alexander Serebrenik: Rewriting Aggregate Queries Using Views. PODS 1999: 155-166
2. Raghu Ramakrishnan, Donko Donjerkovic, Arvind Ranganathan, Kevin S. Beyer, Muralidhar Krishnaprasad: SRQL: Sorted Relational Query Language. SSDBM 1998: 84-95
3. Werner Nutt, Yehoshua Sagiv, Sara Shurin: Deciding Equivalences Among Aggregate Queries. PODS 1998: 214-223
4. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158
5. Gösta Grahne, Nicolas Spyratos, Daniel Stamate: Semantics and Containment with Internal and External Conjunctions. ICDT 1997: 71-82