Rule-based transformation of relational queries into iterative programs

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 specifications 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.

REFERENCES

• ASTR76: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• BELL84: Francoise Bellegarde, Rewriting systems on FP expressions that reduce the number of sequences they yield, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.63-73, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802022]
• BIRD84: R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984 [doi>10.1145/1780.1781]
• BUNE82: Peter Buneman , Robert E. Frankel , Rishiyur Nikhil, An implementation technique for database query languages, ACM Transactions on Database Systems (TODS), v.7 n.2, p.164-186, June 1982 [doi>10.1145/319702.319711]
• BURS77: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• COHE80: Cohen, N H, Source-to-Source improvement of Recurstve Programs, PhD Thesis, Harvard UmversRy (May 1980)
• DANI82: Dames, D, Query Compdatwn tn a Dtstrtbuted Database System, Techmcal Report RJ #3432, IBM Research Laboratoy, San Jose, CA 95193 (March 1982)
• DARL76: Darlmgton, J and Burstall, R M, A System whwh Automattcally Improves Programs, Acta Informatlca 6,1 (January 1976) pp 41-60
• FREY85: Freytag, J C, Translaung Relatwnal Querws into Iteratlve Programs, PhD Thesis, Harvard Umversaty, also Techmcal Report TR-14-85 (September 1985)
• FRIE76: Friedman, D P and Wlese, D S, CONS should not Evaluate tts Arguments, in S Mlchaelson and r Mflner, Automata, Languages, and Programming, Edinburgh Umversaty Press (Edinburgh, 1976) pp 257-284
• GIVL84: John S. Givler , Richard B. Kieburtz, Schema recognition for program transformations, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.74-84, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802023]
• GOLD84: Allen Goldberg , Robert Paige, Stream processing, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.53-62, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802021]
• HUET80: Gérard Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM (JACM), v.27 n.4, p.797-821, Oct. 1980 [doi>10.1145/322217.322230]
• JARK84: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• LORI79: Lone, R A and Wade, B W, The Compdatton of a High Level Data Language, Techmcal Report RJ #2598, IBM Research Laboratory, San Jose, CA 95193 (1979)
• REES82: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• STON76: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]

INDEX TERMS

Classification:
  E. Data
  E.5 FILES
      Subjects: Optimization**

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance