User-defined aggregate functions: bridging theory and practice

ABSTRACT

The ability to create user-defined aggregate functions (UDAs) is rapidly becoming a standard feature in relational database systems. Therefore, problems such as query optimization, query rewriting and view maintenance must take into account queries (or views) with UDAs. There is a wealth of research on these problems for queries with general aggregate functions. Unfortunately, there is a mismatch between the manner in which UDAs are created, and the information that the database system requires in order to apply previous research.The purpose of this paper is to explore this mismatch and to bridge the gap between theory and practice, thereby enabling UDAs to become first-class citizens within the database. Specifically, we consider query optimization, query rewriting and view maintenance for queries with UDAs. For each of these problems we first survey previous results and explore the mismatch between theory and practice. We then present theoretical and practical insights that can be combined to derive a coherent framework for defining UDAs within a database system.

REFERENCES

• 1: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• 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: Sara Cohen , Werner Nutt , Yehoshua Sagiv, Rewriting queries with arbitrary aggregation functions using views, ACM Transactions on Database Systems (TODS), v.31 n.2, p.672-715, June 2006 [doi>10.1145/1138394.1138400]
• 4: 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]
• 5: 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
• 6: 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
• 7: Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.328-339, May 22-25, 1995, San Jose, California, United States
• 8: 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]
• 9: 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
• 10: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 11: 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
• 12: Alon Y. Levy , Inderpal Singh Mumick , Yehoshua Sagiv, Query Optimization by Predicate Move-Around, Proceedings of the 20th International Conference on Very Large Data Bases, p.96-107, September 12-15, 1994
• 13: 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
• 14: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 15: C. Lucchesi and S. Osborn. Candidate keys for relations. JCSS, 17(2):270--279, 1978.
• 16: Mukesh Mohania , Yahiko Kambayashi, Making aggregate views self-maintainable, Data & Knowledge Engineering, v.32 n.1, p.87-109, Jan.1.2000 [doi>10.1016/S0169-023X(99)00016-6]
• 17: Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
• 18: 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
• 19: D. Quass. Maintenance expressions for views with aggregation. In Workshop on Materialized Views, 1996.
• 20: Raghu Ramakrishnan , Kenneth A. Ross , Divesh Srivastava , S. Sudarshan, Efficient incremental evaluation of queries with aggregation, Proceedings of the 1994 International Symposium on Logic programming, p.204-218, November 1994, Symposia, Melbourne
• 21: Kenneth A. Ross , Divesh Srivastava , S. Sudarshan, Materialized view maintenance and integrity constraint checking: trading space for time, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.447-458, June 04-06, 1996, Montreal, Quebec, Canada
• 22: 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
• 23: 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]
• 24: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 25: 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
• 26: 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.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Theory

Keywords:
aggregate queries, query optimization, query rewriting, view maintenance