A Transformation-Based Approach to Optimizing Loops in Database Programming Languages.

Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100

@inproceedings{DBLP:conf/sigmod/LieuwenD92,
  author    = {Daniel F. Lieuwen and
               David J. DeWitt},
  editor    = {Michael Stonebraker},
  title     = {A Transformation-Based Approach to Optimizing Loops in Database
               Programming Languages},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {91-100},
  ee        = {http://doi.acm.org/10.1145/130283.130301, db/conf/sigmod/LieuwenD92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Database programming languages like O₂, E, and O++ include the ability to iterate through a set. Nested iterators can be used to express joins. This paper describes compile-time optirnizations similar to relational transformations like join reordering for such programming constructs. This paper also shows how to use a standard transformation-bssed optimizer to optimize these joins. An optimizer built using the EXODUS Optimizer Generator [GRAE87] was added to the Bell Labs O++ [AGRA89] compiler. We used the resulting optimizing compiler to experimentally validate the ideas in this paper. The experiments show that this technique can significantly improve the performance of database programming languages.

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

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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 DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992

, SIGMOD Record 21(2), June 1992
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1177 KB]

References

[ABU81]: ...
[AGRA89]: Rakesh Agrawal, Narain H. Gehani: Rationale for the Design of Persistence and Query Processing Facilities in the Database Programming Language O++. DBPL 1989: 25-40
[AGRA91]: ...
[ATKI89]: Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik: The Object-Oriented Database System Manifesto. DOOD 1989: 223-240
[DAYA87]: Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
[DEMO85]: G. Barbara Demo, Sukhamay Kundu: Analysis of the Context Dependency of CODASYL Find-Statements with Application to Database Program Conversion. SIGMOD Conference 1985: 354-361
[DEWI84]: David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8
[GANS87]: Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33
[GRAE87]: Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
[KATZ82]: Randy H. Katz, Eugene Wong: Decompiling CODASYL DML into Relational Queries. ACM Trans. Database Syst. 7(1): 1-23(1982)
[KIM82]: Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982)
[LECL89]: Christophe Lécluse, Philippe Richard: The O2 Database Programming Language. VLDB 1989: 411-422
[LIEU91a]: Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305
[LIEU91b]: ...
[LOHM88]: Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
[MURA89]: M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85
[PADU86]: David A. Padua, Michael Wolfe: Advanced Compiler Optimizations for Supercomputers. Commun. ACM 29(12): 1184-1201(1986)
[RIES83]: ...
[RICH89]: ...
[SCHM77]: Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977)
[SELL88]: Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988)
[SHEK90]: Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311
[SHOP80]: ...