Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Rewriting Aggregate Queries Using Views

Sara Cohen, Werner Nutt, and A. Serebrenik

  View Paper (PDF)  

Return to Views/Queries

Abstract
We investigate the problem of rewriting queries with aggregate operators using views that may or may not contain aggregate operators. A rewriting of a query is a second query that uses view predicates such that evaluating first the views and then the rewriting yields the same result as evaluating the original query. In this sense, the original query and the rewriting are equivalent modulo the view definitions. The queries and views we consider correspond to unnested SQL queries, possibly with union, that employ the operators min, max, count, and sum. Our approach is based on syntactic characterizations of the equivalence of aggregate queries. One contribution of this paper are characterizations of the equivalence of disjunctive aggregate queries, which generalize our previous results for the conjunctive case. Rewriting queries using views is a fundamental problem in databases, which has attracted considerable attention. View usability techniques have applications in a number of areas. In query optimization, the execution of a query can be accelerated if results from previous queries can be used to compute answers [YL87, CR94, CKPS95]. In designing information systems over which a huge number of a priori known queries are posed periodically, it can be beneficial to store such intermediate results beforehand that are useful for as many queries as possible [LFS97, RSS96]. Integrating heterogeneous information sources is another problem which may be reduced to the view usability problem (LSK95]. For each operator CZ, we introduce several types of queries using views as candidates for rewritings. We unfold such a candidate by replacing each occurrence of a view predicate with its definition, thus obtaining a regular aggregate query. The candidates have a different, usually more complex operator than LY. We prove that unfolding the candidate, however, results in a regular aggregate query that is equivalent to the candidate modulo the view definitions. This property justifies considering these types of queries as natural candidates for rewritings. In this way, we reduce the problem of whether there exist rewritings of a particular type to a problem involving equivalence. While the focus of this work was for a long time on queries without aggregation, interest in aggregate queries has been motivated recently by the surge of data warehousing and decision support applications, where queries of this kind typically occur. Optimization based on the reuse of previously computed results is particularly promising for aggregate queries, since often huge numbers of data items are processed to produce a single aggregate value. In fact, most existing data warehouses make use of this idea in their optimization algorithms in a more or less ad hoc way [Kim96]. We distinguish between partial rewritings that contain at least one view predicate and complete rewritings that contain only view predicates. In contrast to previous work on this topic, we not only give sufficient, but also necessary conditions for a rewriting to exist. More precisely, we show for each type of candidate that the existence of both, partial and complete rewritings is decidable, and we provide upper and lower complexity bounds.


References

Note: References link to DBLP on the 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
[CR94]
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
[CV93]
Surajit Chaudhuri , Moshe Y. Vardi : Optimization of Real Conjunctive Queries. PODS 1993 : 59-70
[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)
[Kim96]
Ralph Kimball : The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses. John Wiley 1996, ISBN 0-471-15337-0
[LFS97]
François Llirbat , Françoise Fabret , Eric Simon : Eliminating Costly Redundant Computations from SQL Trigger Executions. SIGMOD Conference 1997 : 428-439
[LMSS93]
Alon Y. Levy , Inderpal Singh Mumick , Yehoshua Sagiv , Oded Shmueli : Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993 : 109-122
[LMSS95]
Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104
[LS95]
Alon Y. Levy , Yehoshua Sagiv : Semantic Query Optimization in Datalog Programs. PODS 1995 : 163-173
[LSK95]
Alon Y. Levy , Divesh Srivastava , Thomas Kirk : Data Model and Query Evaluation in Global Information Systems. JIIS 5(2) : 121-143(1995)
[NSS98]
Werner Nutt , Yehoshua Sagiv , Sara Shurin : Deciding Equivalences Among Aggregate Queries. PODS 1998 : 214-223
[RSS96]
Kenneth A. Ross , Divesh Srivastava , S. Sudarshan : Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conf. 1996 : 447-458
[SDJL96]
Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy : Answering Queries with Aggregation Using Views. VLDB 1996 : 318-329
[SS92]
...
[SY81]
Yehoshua Sagiv , Mihalis Yannakakis : Equivalences Among Relational Expressions with the Union and Difference Operators. JACM 27(4) : 633-655(1980)
[Ull88]
Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[vdM92]
Ron van der Meyden : The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992 : 331-345
[YL87]
H. Z. Yang , Per-Åke Larson : Query Transformation for PSJ-Queries. VLDB 1987 : 245-254

Referenced by

  1. Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Rewriting of Regular Expressions and Regular Path Queries. PODS 1999 : 194-204

BIBTEX

@inproceedings{DBLP:conf/pods/CohenNS99,
  author    = {Sara Cohen and
                Werner Nutt and
                A. Serebrenik},
   title     = {Rewriting Aggregate Queries Using Views},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {155-166},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM