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

Rule Languages and Internal Algebras for Rule-Based Optimizers.

Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
@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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

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

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1453 KB]

References

[1]
...
[2]
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers: Princiles, Techniques, and Tools. Addison-Wesley 1986, ISBN 0-201-10088-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Annalisa Bossi, Carlo Ghezzi: Using FP As a Query Language for Relational Data-Bases. Comput. Lang. 9(1): 25-37(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Peter Buneman, Robert E. Frankel: FQL - A Functional Query Language. SIGMOD Conference 1979: 52-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
R. G. G. Cattell: The Object Database Standard: ODMG-93. Morgan Kaufmann 1993, ISBN 1-55860-302-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
...
[12]
Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Martin Erwig, Udo W. Lipeck: A Functional DBPL Revealing High Level Optimizations. DBPL 1991: 306-321 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Leonidas Fegaras, David Maier, Tim Sheard: Specifying Rule-Based Query Optimizers in a Reflective Framework. DOOD 1993: 146-168 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Georges Gardarin, Fernando Machuca, Philippe Pucheral: OFL: A Functional Execution Model for Object Query Languages. SIGMOD Conference 1995: 59-70 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
...
[22]
...
[23]
Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
...
[28]
...
[29]
...
[30]
M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[33]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
...
[35]
Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[37]
D. A. Turner: A New Implementation Technique for Applicative Languages. Softw., Pract. Exper. 9(1): 31-49(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[38]
Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:21:33 2010 by Michael Ley (ley@uni-trier.de)