 |
|
|
Deciding Equivalences Among Aggregate Queries |
Full Paper (PDF)
Slides (PDF)
Equivalence of aggregate queries is investigated for the class of conjunctive queries with comparisons and the aggregate operators min, max, count, count-distinct, and sum. Essentially, this class contains all unnested SQL queries with the above aggregate operators, with a WHERE clause consisting of a conjunction of comparisons, and without a HAVING clause. The comparisons can be interpreted over either a dense order (e.g., over the rationals) or a discrete order (e.g., over the integers). Generally, however, different techniques and characterizations are needed in each of these two cases.
For queries with either max or min, equivalence is characterized in terms of dominance mappings, which can be viewed as a generalization of containment mappings. For queries with the count-distinct operator, a sufficient condition for equivalence is given in terms of equivalence of conjunctive queries under set semantics. For some special cases, it is shown that this condition is also necessary. For conjunctive queries with comparisons but without aggregation, equivalence under bag-set semantics is characterized in terms of isomorphism. This characterization essentially remains the same also for queries with the count operator. Moreover, this characterization also applies to queries with the sum operator if the queries have either constants or comparisons, but not both. In the general case (i.e., both comparisons and constants), the characterization of the equivalence of queries with the sum operator is more elaborate. All the characterizations given in the paper are decidable with with polynomial space.
Finally, it is shown that all the characterizations for min-, max-, count-, and sum-queries yield polynomial-time algorithms for linear queries, i.e., queries with no repeated predicates in their bodies. |
References, where available, link to the DBLP on the World Wide Web.
[ASU79]Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Efficient Optimization of a Class of Relational Expressions.
TODS 4(4): 435-454(1979)[CKPS95]Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim:
Optimizing Queries with Materialized Views.
ICDE 1995: 190-200[CM77]Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90[CV93]Surajit Chaudhuri, Moshe Y. Vardi:
Optimization of Real Conjunctive Queries.
PODS 1993: 59-70[DJLS96]Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy:
Answering Queries with Aggregation Using Views.
VLDB 1996: 318-329[GHQ95]Ashish Gupta, Venky Harinarayan, Dallan Quass:
Aggregate-Query Processing in Data Warehousing Environments.
VLDB 1995: 358-369[IR95]Yannis E. Ioannidis, Raghu Ramakrishnan:
Containment of Conjunctive Queries: Beyond Relations as Sets.
TODS 20(3): 288-324(1995)[JK83]David S. Johnson, Anthony C. Klug:
Optimizing Conjunctive Queries that Contain Untyped Variables.
SIAM J. Comput. 12(4): 616-640(1983)[LMSS93]Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli:
Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions.
PODS 1993: 109-122[LS95]Alon Y. Levy, Yehoshua Sagiv:
Semantic Query Optimization in Datalog Programs.
PODS 1995: 163-173[RSSS98]...
[SS92]...
[SY81]Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
JACM 27(4): 633-655(1980)[vdM92]Ron van der Meyden:
The Complexity of Querying Indefinite Data about Linearly Ordered Domains.
PODS 1992: 331-345
|
@inproceedings{DBLP:conf/pods/NuttSS98,
author = {Werner Nutt and
Yehoshua Sagiv and
Sara Shurin},
title = {Deciding Equivalences Among Aggregate Queries},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {214-223},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
