ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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}
}
BibTeX

Abstract

Database programming languages like O2, 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 ...

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

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 BibTeX , 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 BibTeX
[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 BibTeX
[DAYA87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
[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 BibTeX
[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 BibTeX
[GANS87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
[GRAE87]
Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
BibTeX
[KATZ82]
Randy H. Katz, Eugene Wong: Decompiling CODASYL DML into Relational Queries. ACM Trans. Database Syst. 7(1): 1-23(1982) BibTeX
[KIM82]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[LECL89]
Christophe Lécluse, Philippe Richard: The O2 Database Programming Language. VLDB 1989: 411-422 BibTeX
[LIEU91a]
Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305 BibTeX
[LIEU91b]
...
[LOHM88]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX
[MURA89]
M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85 BibTeX
[PADU86]
David A. Padua, Michael Wolfe: Advanced Compiler Optimizations for Supercomputers. Commun. ACM 29(12): 1184-1201(1986) BibTeX
[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) BibTeX
[SELL88]
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
[SHEK90]
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 BibTeX
[SHOP80]
...

Referenced by

  1. Daniel F. Lieuwen: Parallelizing Loops in Database Programming Languages. ICDE 1998: 86-93
  2. Alexandra Poulovassilis, Carol Small: Algebraic Query Optimisation for Database Programming Languages. VLDB J. 5(2): 119-132(1996)
  3. Alexandra Poulovassilis, Carol Small: Investigation of Algebraic Query Optimisation Techniques for Database Programming Languages. VLDB 1994: 415-426
  4. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  5. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
  6. Rakesh Agrawal, Shaul Dar, Narain H. Gehani: The O++ Database Programming Language: Implementation and Experience. ICDE 1993: 61-70
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:09 2009