Rewriting queries with arbitrary aggregation functions using views

ABSTRACT

The problem of rewriting aggregate queries using views is studied for conjunctive queries with arbitrary aggregation functions and built-in predicates. Two types of queries over views are introduced for rewriting aggregate queries: pure candidates and aggregate candidates. Pure candidates can be used to rewrite arbitrary aggregate queries. Aggregate candidates can be used to rewrite queries containing aggregate functions definable in terms of a commutative-semigroup operation. For both types of candidates (as well as for several relaxations of these candidates), the unfolding property holds. This allows characterizations for query equivalence to be used to determine whether a candidate is a rewriting of a query. The complexity of the rewriting-existence problem is also studied and upper and lower complexity bounds are given.

REFERENCES

• 1: Afrati, F. and Chirkova, R. 2005. Selecting and using views to compute aggregate queries. In Proceedings of the 10th International Conference on Database Theory (Edinburgh, UK). Lecture Notes in Computer Science. Springer-Verlag, New York.
• 2: Surajit Chaudhuri , Kyuseok Shim, Optimizing Queries with Aggregate Views, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.167-182, March 25-29, 1996
• 3: Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
• 4: Cohen, S. 2004. Equivalence, containment and rewriting of aggregate queries. Ph.D. dissertation, The Hebrew University of Jerusalem, Edmond J. Safra Campus, Jerusalem 91904, Israel. Available at http://iew3.technion.ac.il/~sarac.
• 5: Sara Cohen, Containment of aggregate queries, ACM SIGMOD Record, v.34 n.1, March 2005 [doi>10.1145/1058150.1058170]
• 6: Sara Cohen , Werner Nutt , Yehoshua Sagiv, Containment of Aggregate Queries, Proceedings of the 9th International Conference on Database Theory, p.111-125, January 08-10, 2003
• 7: Sara Cohen , Yehoshua Sagiv , Werner Nutt, Equivalences among aggregate queries with negation, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.328-360, April 2005 [doi>10.1145/1055686.1055691]
• 8: Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303992]
• 9: Sara Cohen , Werner Nutt , Alexander Serebrenik, Algorithms for Rewriting Aggregate Queries Using Views, Proceedings of the East-European Conference on Advances in Databases and Information Systems Held Jointly with International Conference on Database Systems for Advanced Applications: Current Issues in Databases and Information Systems, p.65-78, September 05-08, 2000
• 10: Cohen, S., Nutt, W., and Serebrenik, A. 2000b. Algorithms for rewriting aggregate queries using views. Tech. Rep. CW292, Departement Computerwetenschappen, K.U. Leuven, Leuven, Belgium. Available at http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW292.abs.html.
• 11: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 12: Florescu, D., Raschid, L., and Valduriez, P. 1995. Using heterogeneous equivalences for query rewriting in multidatabase systems. In Proceedings of the 3rd International Conference on Cooperative Information Systems (CoopIS) (Vienna, Austria). 158--169.
• 13: César Galindo-Legaria , Milind Joshi, Orthogonal optimization of subqueries and aggregation, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.571-581, May 21-24, 2001, Santa Barbara, California, United States
• 14: Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.331-342, May 21-24, 2001, Santa Barbara, California, United States
• 15: Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, Querying aggregate data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.174-184, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303994]
• 16: Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, On the equivalence and rewriting of aggregate queries, Acta Informatica, v.40 n.8, p.529-584, July 2004 [doi>10.1007/s00236-004-0101-y]
• 17: Stéphane Grumbach , Leonardo Tininini, On the content of materialized aggregate views, Journal of Computer and System Sciences, v.66 n.1, p.133-168, 01 February 2003 [doi>10.1016/S0022-0000(02)00033-8]
• 18: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• 19: Ashish Gupta , Iderpal Singh Mumick, Materialized views: techniques, implementations, and applications, MIT Press, Cambridge, MA, 1999
• 20: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 21: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 22: Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, New York.
• 23: Larson, P.-A. and Yang, H. 1985. Computing queries from derived relations. In Proceedings of the 11th International Conference on Very Large Data Bases (Stockholm, Sweden), A. Pirotte and Y. Vassiliou, Eds. Morgan-Kaufmann, San Francisco, CA, 259--269.
• 24: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 25: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 26: Alon Y. Levy , Divesh Srivastava , Thomas Kirk, Data model and query evaluation in global information systems, Journal of Intelligent Information Systems, v.5 n.2, p.121-143, Sept. 1995 [doi>10.1007/BF00962627]
• 27: Werner Nutt , Yehoshus Sagiv , Sara Shurin, Deciding equivalences among aggregate queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-223, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275512]
• 28: Rachel Pottinger , Alon Halevy, MiniCon: A scalable algorithm for answering queries using views, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.182-198, September 2001
• 29: Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
• 30: R. Ramakrishnan , Y. Sagiv , J. D. Ullman , M. Y Vardi, Proof-tree transformation theorems and their applications, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73739]
• 31: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 32: Dimitri Theodoratos , Timos Sellis, Answering Multidimensional Queries on Cubes Using Other Cubes, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.109, July 26-28, 2000 [doi>10.1109/SSDM.2000.869782]
• 33: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996 [doi>10.1007/s007780050018]
• 34: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 35: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 36: Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995
• 37: H. Z. Yang , Per-Åke Larson, Query Transformation for PSJ-Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.245-254, September 01-04, 1987
• 38: Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.105-116, May 15-18, 2000, Dallas, Texas, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Languages, Theory

Keywords:
View usability, query equivalence, query rewriting