Rule-Based Translation of Relational Queries into Iterative Programs.

@inproceedings{DBLP:conf/sigmod/FreytagG86,
  author    = {Johann Christoph Freytag and
               Nathan Goodman},
  editor    = {Carlo Zaniolo},
  title     = {Rule-Based Translation of Relational Queries into Iterative Programs},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {206-214},
  ee        = {http://doi.acm.org/10.1145/16894.16875, db/conf/sigmod/FreytagG86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Over the last decade many techniques for optimizing relational queries have been developed. However, the problem of translating these set-oriented query specifications into other forms for efficient execution has received little attention.

This paper presents an algorithm that translates algebra-based query speciftcations into iterative programs for an efficient execution. While the source level operates on sets of tuples, the generated programs manipulate tuples as their basic objects. The algorithm incorporates techniques which have been developed in the areas of functional programming and program transformation.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 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

Online Edition: ACM Digital Library

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)

[BELL84]

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

[BIRD84]

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

[BUNE82]

Peter Buneman, Robert E. Frankel, Rishiyur S. Nikhil: An Implementation Technique for Database Query Languages. ACM Trans. Database Syst. 7(2): 164-186(1982)

[BURS77]

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

[COHE80]

...

[DANI82]

...

[DARL76]

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

[FREY85]

...

[FRIE76]

Daniel P. Friedman, David S. Wise: CONS Should Not Evaluate its Arguments. ICALP 1976: 257-284

[GIVL84]

...

[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)

[JARK84]

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

[LORI79]

...

[REES82]

...

[STON76]

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