Rule Languages and Internal Algebras for Rule-Based Optimizers.

@inproceedings{DBLP:conf/sigmod/CherniackZ96,
  author    = {Mitch Cherniack and
               Stanley B. Zdonik},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Rule Languages and Internal Algebras for Rule-Based Optimizers},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {401-412},
  ee        = {http://doi.acm.org/10.1145/233269.233356, db/conf/sigmod/CherniackZ96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Rule-based optimizer generators use rules to specify query transformations. Rules act directly on query representations, which are typically based on query algebras. But most algebras complicate rule formulation, and rules over these algebras must often resort to calling to externally defined bodies of code. Code makes it difficult to formulate, prove correct and reason about, and therefore compromises the effectiveness of rule-based systems.

In this paper we present KOLA; a combinator-based algebra designed to simplify rule formulation. KOLA is not a user language, and KOLA's variable-free queries are difficult for humans to read. But KOLA is an effective internal algebra because its combinator-style makes queries manipulable and structurally revealing. As a result, rules over KOLA queries are easily expressed without the need for supplemental code. We illustrate this point, first by showing some transformation that despite their simplicity, require head and body routines when expressed over algebras that include variables. We show that these transformations are expressible without supplemental routines in KOLA. We then show complex transformations of a class of nested queries expressed over KOLA. Nested query optimizations, while having been studied before, have seriously challenged the rule-based paradigm.

Copyright © 1996 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

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" 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/smod9397 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/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

...

[2]

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers: Princiles, Techniques, and Tools. Addison-Wesley 1986, ISBN 0-201-10088-6
BibTeX

[3]

John W. Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. Commun. ACM 21(8): 613-641(1978) BibTeX

[4]

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

[5]

Annalisa Bossi, Carlo Ghezzi: Using FP As a Query Language for Relational Data-Bases. Comput. Lang. 9(1): 25-37(1984) BibTeX

[6]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[7]

Peter Buneman, Robert E. Frankel: FQL - A Functional Query Language. SIGMOD Conference 1979: 52-58 BibTeX

[8]

...

[9]

R. G. G. Cattell: The Object Database Standard: ODMG-93. Morgan Kaufmann 1993, ISBN 1-55860-302-6
BibTeX

[10]

...

[11]

...

[12]

Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242 BibTeX

[13]

...

[14]

Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX

[15]

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

[16]

Leonidas Fegaras, David Maier, Tim Sheard: Specifying Rule-Based Query Optimizers in a Reflective Framework. DOOD 1993: 146-168 BibTeX

[17]

Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX

[18]

Georges Gardarin, Fernando Machuca, Philippe Pucheral: OFL: A Functional Execution Model for Object Query Languages. SIGMOD Conference 1995: 59-70 BibTeX

[19]

...

[20]

Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 BibTeX

[21]

...

[22]

...

[23]

Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554 BibTeX

[24]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[25]

Theodore W. Leung, Gail Mitchell, Bharathi Subramanian, Bennet Vance, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Data Model and Algebra. DBPL 1993: 157-175 BibTeX

[26]

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX

[27]

...

[28]

...

[29]

...

[30]

M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85 BibTeX

[31]

M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 BibTeX

[32]

John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX

[33]

Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX

[34]

...

[35]

Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153 BibTeX

[36]

Dave D. Straube, M. Tamer Özsu: Queries and Query Processing in Object-Oriented Database Systems. ACM Trans. Inf. Syst. 8(4): 387-430(1990) BibTeX

[37]

D. A. Turner: A New Implementation Technique for Applicative Languages. Softw., Pract. Exper. 9(1): 31-49(1979) BibTeX

[38]

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

Referenced by

1. Peter A. Boncz, Martin L. Kersten: MIL Primitives for Querying a Fragmented World. VLDB J. 8(2): 101-119(1999)
2. Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
3. Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57
4. Praveen Seshadri: Enhanced Abstract Data Types in Object-Relational Databases. VLDB J. 7(3): 130-140(1998)
5. Mitch Cherniack, Stanley B. Zdonik: Inferring Function Semantics to Optimize Queries. VLDB 1998: 239-250
6. Mitch Cherniack, Stanley B. Zdonik: Changing the Rules: Transformations for Rule-Based Optimizers. SIGMOD Conference 1998: 61-72
7. Peter A. Boncz, Annita N. Wilschut, Martin L. Kersten: Flattening an Object Algebra to Provide Performance. ICDE 1998: 568-577
8. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: The Case for Enhanced Abstract Data Types. VLDB 1997: 66-75
9. Hamid Pirahesh, T. Y. Cliff Leung, Waqar Hasan: A Rule Engine for Query Transformation in Starburst and IBM DB2 C/S DBMS. ICDE 1997: 391-400
10. Mitch Cherniack, Stanley B. Zdonik, Marian H. Nodine: To Form a More Perfect Union (Intersection, Difference). DBPL 1995: 6