A tool supporting query optimization and program transformation techniques

ABSTRACT

In this paper we propose the integration of query optimization and program transformation technologies in a second generation optimizer generator called OG. The input to OG is a high-level specification of the strategy transformations done by each module of a query optimizer. OG's design is intended to support the specification and automatic implementation of extensions to data-access languages.

REFERENCES

• Aho1979: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• Astr1976: 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]
• Baue1989: Friedrich Ludwig Bauer , Bernhard Möller , Helmut Partsch , Peter Pepper, Formal Program Construction by Transformations-Computer-Aided, Intuition-Guided Programming, IEEE Transactions on Software Engineering, v.15 n.2, p.165-180, February 1989 [doi>10.1109/32.21743]
• Ders1989: Proceedings of the 3rd International Conference on Rewriting Techniques and Applications, April 1989
• Feat1982: Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
• Feat1987: M. S. Feather, "Program Transformation: A Survey and Classification," in Program Specification and Transformation, ed. L. G. L. T. Meertens, pp. 165-195, North- Holland, Amsterdam, 1987.
• Frey1986: Johann Christoph Freytag , Nathan Goodman, Rule-based transformation of relational queries into iterative programs, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.206-214, May 28-30, 1986, Washington, D.C., United States
• Frey1987: Johann Christoph Freytag, A rule-based view of query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.173-180, May 27-29, 1987, San Francisco, California, United States
• Grae1987: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• Haas1989: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• Huet1980: 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]
• Joua1985: Jean-Pierre Jouannaud, Rewriting Techniques and Applications, Academic Press, Inc., Orlando, FL, 1988
• Lee1988: Mavis K. Lee , Johann Christoph Freytag , Guy M. Lohman, Implementing an Interpreter for Functional Rules in a Query Optimizer, Proceedings of the 14th International Conference on Very Large Data Bases, p.218-229, August 29-September 01, 1988
• Lesc1987: Proceedings of the 2nd International Conference on Rewriting Techniques and Applications, May 1987
• Lohm1988: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• O’D1985: Michael J. O'Donnell, Equational logic as a programming language, Massachusetts Institute of Technology, Cambridge, MA, 1985
• Paig1982: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• Part1983: H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983 [doi>10.1145/356914.356917]
• Rose1987: A. Rosenthal and P. Helman, "Understanding and Extending Transformation-Based Optimizers," Database Engineering, vol. 9, no. 4, pp. 44-5 i, Dec. 1987.
• Ston1976: 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]
• Ullm1985: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Design, Languages, Performance