On the Translation of Relational Queries into Iterative Programs.

@article{DBLP:journals/tods/FreytagG89,
  author    = {Johann Christoph Freytag and
               Nathan Goodman},
  title     = {On the Translation of Relational Queries into Iterative Programs},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {1},
  year      = {1989},
  pages     = {1-27},
  ee        = {http://doi.acm.org/10.1145/62032.62033, db/journals/tods/FreytagG89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper investigates the problem of translating set-oriented query specifications into iterative programs. The translation uses techniques of functional programming and program transformation.

We present two algorithms that generate iterative programs from algebra-based query specifications. The first algorithm translates query specifications into recursive programs. Those are simplified by sets of transformation rules before the algorithm generates the final iterative form. The second algorithm uses a two-level translation that generates iterative programs faster than the first algorithm. On the first level a small set of transformation rules performs structural simplification before the functional combination on the second level yields the final iterative form.

Copyright © 1989 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.

Joint ACM SIGMOD / IEEE Computer Society 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/An3-1 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/aDVD2 or /dvd

References

[1]

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

[2]

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

[3]

...

[4]

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

[5]

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

[6]

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

[7]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[8]

...

[9]

L. Colussi: Recursion As an Effective Step in Program Development. ACM Trans. Program. Lang. Syst. 6(1): 55-67(1984) BibTeX

[10]

...

[11]

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

[12]

...

[13]

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

[14]

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

[15]

...

[16]

Peter Henderson, James H. Morris Jr.: A Lazy Evaluator. POPL 1976: 95-103 BibTeX

[17]

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

[18]

...

[19]

Albert R. Meyer: What is a Model of the Lambda Calculus? Information and Control 52(1): 87-122(1982) BibTeX

[20]

Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255 BibTeX

[21]

...

[22]

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

[23]

...

[24]

Robert D. Tennent: The Denotational Semantics of Programming Languages. Commun. ACM 19(8): 437-453(1976) BibTeX

[25]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[26]

...

Referenced by

1. Till Westmann, Donald Kossmann, Sven Helmer, Guido Moerkotte: The Implementation and Performance of Compressed Databases. SIGMOD Record 29(3): 55-67(2000)
2. Alexandra Poulovassilis, Carol Small: Algebraic Query Optimisation for Database Programming Languages. VLDB J. 5(2): 119-132(1996)
3. Andreas Gawecki, Florian Matthes: Exploiting Persistent Intermediate Code Representations in Open Database Environments. EDBT 1996: 403-423
4. Xiaolei Qian: The Deductive Synthesis of Database Transactions. ACM Trans. Database Syst. 18(4): 626-677(1993)
5. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
6. Leonidas Fegaras: Efficient Optimization of Iterative Queries. DBPL 1993: 200-225
7. Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
8. Steve Rozen, Dennis Shasha: A Framework for Automating Physical Database Design. VLDB 1991: 401-411
9. Xiaolei Qian: Synthesizing Database Transactions. VLDB 1990: 552-565
10. Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88