Translating Aggregate Queries into Iterative Programs.

@inproceedings{DBLP:conf/vldb/Freytag86,
  author    = {Johann Christoph Freytag and
               Nathan Goodman},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Translating Aggregate Queries into Iterative Programs},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {138-146},
  ee        = {db/conf/vldb/Freytag86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Over the last decade, many techniques for optimizing relational queries have been developed. However, the optimization of queries with aggregation has received little attention.

This paper investigates possible improvements for aggregate queries on groups of tuples. We suggest the use of program transformation methods to systematically generate efficient iterative programs for their evaluation. Two transformation steps successively translate a program, which sorts the relation before applying the aggregate function, into an iterative program which performs the aggregation while sorting, thus using less time and space than needed for the execution of the initial program.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD 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/vldb7588 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/aDVD1 or /dvd

Printed Edition

References

[ASTR76]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX

[BACK78]

John W. Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. Commun. ACM 21(8): 613-641(1978) BibTeX

[BELL84]

Françoise Bellegarde: Rewriting Systems on FP Expressions to Reduce the Number of Sequences Yielded. Sci. Comput. Program. 6(1): 11-34(1986) BibTeX

[BIRD84]

Richard S. Bird: The Promotion and Accumulation Strategies in Transformational Programming. ACM Trans. Program. Lang. Syst. 6(4): 487-504(1984) BibTeX

[BITT83]

Dina Bitton, David J. DeWitt: Duplicate Record Elimination in Large Data Files. ACM Trans. Database Syst. 8(2): 255-265(1983) BibTeX

[BURS77]

Rod M. Burstall, John Darlington: A Transformation System for Developing Recursive Programs. J. ACM 24(1): 44-67(1977) BibTeX

[COHE80]

...

[DARL76]

John Darlington, Rod M. Burstall: A System which Automatically Improves Programs. Acta Inf. 6: 41-60(1976) BibTeX

[FREY85a]

...

[FREY85b]

Johann Christoph Freytag, Nathan Goodman: Rule-Based Translation of Relational Queries into Iterative Programs. SIGMOD Conference 1986: 206-214 BibTeX

[GOLD84]

...

[HUET80]

Gérard P. Huet: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems. J. ACM 27(4): 797-821(1980) BibTeX

[JARK84]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX

[KLUG82]

Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173 BibTeX

[KNUT73]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[STON76]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[WILL82]

...

Referenced by

1. Jose Alvin G. Gendrano, Bruce C. Huang, Jim M. Rodrigue, Bongki Moon, Richard T. Snodgrass: Parallel Algorithms for Computing Temporal Aggregates. ICDE 1999: 418-427
2. Nick Kline, Richard T. Snodgrass: Computing Temporal Aggregates. ICDE 1995: 222-231
3. Richard T. Snodgrass, Santiago Gomez, L. Edwin McKenzie: Aggregates in the Temporal Query Language TQuel. IEEE Trans. Knowl. Data Eng. 5(5): 826-842(1993)
4. Don S. Batory, T. Y. Leung, T. E. Wise: Implementation Concepts for an Extensible Data Model and Data Language. ACM Trans. Database Syst. 13(3): 231-262(1988)
5. Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180