Algebraic Query Optimisation for Database Programming Languages.

@article{DBLP:journals/vldb/PoulovassilisS96,
  author    = {Alexandra Poulovassilis and
               Carol Small},
  title     = {Algebraic Query Optimisation for Database Programming Languages},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {2},
  year      = {1996},
  pages     = {119-132},
  ee        = {db/journals/vldb/PoulovassilisS96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A major challenge still facing the designers and implementors of database programming languages (DBPLs) is that of query optimisation. We investigate algebraic query optimisation techniques for DBPLs in the context of a purely declarative functional language that supports sets as first-class objects. Since the language is computationally complete issues such as non-termination of expressions and construction of infinite data structures can be investigated, whilst its declarative nature allows the issue of side effects to be avoided and a richer set of equivalences to be developed. The language has a well-defined semantics which permits us to reason formally about the properties of expressions, such as their equivalence with other expressions and their termination. The support of a set bulk data type enables much prior work on the optimisation of relational languages to be utilised.

In the paper we first give the syntax of our archetypal DBPL and briefly discuss its semantics. We then define a small but powerful algebra of operators over the set data type, provide some key equivalences for expressions in these operators, and list transformation principles for optimising expressions. Along the way, we identify some caveats to well-known equivalences for non-deductive database languages. We next extend our language with two higher level constructs commonly found in functional DBPLs: set comprehensions and functions with known inverses. Some key equivalences for these constructs are provided, as are transformation principles for expressions in them. Finally, we investigate extending our equivalences for the set operators to the analogous operators over bags. Although developed and formally proved in the context of a functional language, our findings are directly applicable to other DBPLs of similar expressiveness.

Key Words

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Conference Version

ACM SIGMOD 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/An4-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]

Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219 BibTeX

[2]

Lennart Augustsson: A Compiler for Lazy ML. LISP and Functional Programming 1984: 218-227 BibTeX

[3]

François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105 BibTeX

[4]

Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88 BibTeX

[5]

Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190 BibTeX

[6]

...

[7]

Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX

[8]

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

[9]

Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366 BibTeX

[10]

Chris D. Clack, Simon L. Peyton Jones: Strictness Analysis - A Practical Approach. FPCA 1985: 35-49 BibTeX

[11]

Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392 BibTeX

[12]

Birgit Demuth, Andreas Geppert, Thorsten Gorchs: Algebraic Query Optimization in the CoOMS Structurally Object-Oriented Database System. Query Processing for Advanced Database Systems, Dagstuhl 1991: 121-142 BibTeX

[13]

Martin Erwig, Udo W. Lipeck: A Functional DBPL Revealing High Level Optimizations. DBPL 1991: 306-321 BibTeX

[14]

Johann Christoph Freytag, Nathan Goodman: On the Translation of Relational Queries into Iterative Programs. ACM Trans. Database Syst. 14(1): 1-27(1989) BibTeX

[15]

Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163 BibTeX

[16]

Peter G. Harrison, Hessam Khoshnevisan: The Mechanical Transformation of Data Types. Comput. J. 35(2): 138-147(1992) BibTeX

[17]

...

[18]

J. Roger Hindley, Jonathan P. Seldin: Introduction to Combinators and Lambda-Calculus. Cambridge University Press 1986
BibTeX

[19]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX

[20]

...

[21]

Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 BibTeX

[22]

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

[23]

Atsushi Ohori, Peter Buneman, Val Tannen: Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989: 46-57 BibTeX

[24]

Norman W. Paton, Peter M. D. Gray: Optimising and Executing DAPLEX Queries Using Prolog. Comput. J. 33(6): 547-555(1990) BibTeX

[25]

...

[26]

Simon L. Peyton Jones: The Implementation of Functional Programming Languages. Prentice-Hall 1987
BibTeX

[27]

Gordon D. Plotkin: A Powerdomain Construction. SIAM J. Comput. 5(3): 452-487(1976) BibTeX

[28]

Alexandra Poulovassilis, Carol Small: A Domain-theoretic Approach to Integrating Functional and Logic Database Languages. VLDB 1993: 416-428 BibTeX

[29]

...

[30]

Gail M. Shaw, Stanley B. Zdonik: An Object-Oriented Query Algebra. DBPL 1989: 103-112 BibTeX

[31]

Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991: 2-11 BibTeX

[32]

...

[33]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[34]

Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 BibTeX

[35]

Philip Wadler: Comprehending Monads. LISP and Functional Programming 1990: 61-78 BibTeX

Referenced by

1. Luca Cabibbo, Riccardo Torlone: A Framework for the Investigation of Aggregate Functions in Database Queries. ICDT 1999: 383-397
2. Alexandra Poulovassilis, Carol Small: Formal Foundations for Optimising Aggregation Functions in Database Programming Languages. DBPL 1997: 299-318