Rule-Based Translation of Relational Queries into Iterative Programs.

Johann Christoph Freytag, Nathan Goodman: Rule-Based Translation of Relational Queries into Iterative Programs. SIGMOD Conference 1986: 206-214
  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        = {, db/conf/sigmod/FreytagG86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP,}


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

Online Version (ACM WWW Account required): Full Text in PDF Format

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986 BibTeX , SIGMOD Record 15(2)

Online Edition: ACM Digital Library


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
Françoise Bellegarde: Rewriting Systems on FP Expressions to Reduce the Number of Sequences Yielded. Sci. Comput. Program. 6(1): 11-34(1986) BibTeX
Richard S. Bird: The Promotion and Accumulation Strategies in Transformational Programming. ACM Trans. Program. Lang. Syst. 6(4): 487-504(1984) BibTeX
Peter Buneman, Robert E. Frankel, Rishiyur S. Nikhil: An Implementation Technique for Database Query Languages. ACM Trans. Database Syst. 7(2): 164-186(1982) BibTeX
Rod M. Burstall, John Darlington: A Transformation System for Developing Recursive Programs. J. ACM 24(1): 44-67(1977) BibTeX
John Darlington, Rod M. Burstall: A System which Automatically Improves Programs. Acta Inf. 6: 41-60(1976) BibTeX
Daniel P. Friedman, David S. Wise: CONS Should Not Evaluate its Arguments. ICALP 1976: 257-284 BibTeX
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
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

Referenced by

  1. Bennet Vance: An Abstract Object-Oriented Query Execution Language. DBPL 1993: 176-199
  2. Béatrice Finance, Georges Gardarin: A Rule-Based Query Rewriter in an Extensible DBMS. ICDE 1991: 248-256
  3. HweeHwa Pang, Hongjun Lu, Beng Chin Ooi: Query Processing in OODB. DASFAA 1991: 1-10
  4. Johann Christoph Freytag, Nathan Goodman: On the Translation of Relational Queries into Iterative Programs. ACM Trans. Database Syst. 14(1): 1-27(1989)
  5. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  6. 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)
  7. Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172
  8. Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180
  9. Johann Christoph Freytag, Nathan Goodman: Translating Aggregate Queries into Iterative Programs. VLDB 1986: 138-146
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:45 2009