Mitch Cherniack
ABSTRACT
Rule-based optimizers are extensible because they consist of modifiable sets of rules. For modification to be straightforward, rules must be easily reasoned about (i.e., understood and verified). At the same time, rules must be expressive and efficient (to fire) for rule-based optimizers to be practical. Production-style rules (as in [15]) are expressed with code and are hard to reason about. Pure rewrite rules (as in [1]) lack code, but cannot atomically express complex transformations (e.g., normalizations). Some systems allow rules to be grouped, but sacrifice efficiency by providing limited control over their firing. Therefore, none of these approaches succeeds in making rules expressive, efficient and understandable.
We propose a language (COKO) for expressing an alternative form of input to a rule-based optimizer. A COKO transformation consists of a set of declarative (KOLA) rewrite rules and a (firing) algorithm that specifies their firing. It is straightforward to reason about COKO transformations because all query modification is expressed with declarative rewrite rules. Firing is specified algorithmically with an expressive language that provides direct control over how query representations are traversed, and under what conditions rules are fired. Therefore, COKO achieves a delicate balance of understandability, efficiency and expressivity.
- 1.L. Becket and R. H. GOring. Rule-based optimization and query processing in an extensible geometric database system. ACM Transactions on Database Systems, 17(2):247-303, June ! 992. Google Scholar
Digital Library
- 2.M. J. Care),, D. J. DcWitt, G. Graefe, D. M. Haight, J. E. Richardson, D. T. Schuh, E. J. Shekita, and S. L. Vandenberg. The EXODUS extensible DBMS project: An overview. In S. B. Zdonik and D. Maier, editors, Readings in Object- Oriented Database Systems, pages 474-499. Morgan Kaufmann Publishers, Inc., Los Altos, California, 1990. Google ScholarDigital Library
- 3.M. Chemiack Translating queries into combinators. September 1996.Google Scholar
- 4.M. CheraiacL Building query optimizers with combinators. Ph.D. Dissertation Proposal. Brown University, 1997. Google ScholarDigital Library
- 5.M. Chemiack and S. B. Zdonik. Rule languages and internal algebras for rulebased optimizers. In Proc. ACM SIGMOD int'l Conference on Management of Data, Montreal, Qu6bec, Canada, June 1996. Google ScholarDigital Library
- 6.B. Finance and G. Gardarin. A rule-based query rewriter in an extensible dbms. In Proceedings of the Seventh international Conference on Data Engineering, pages 248-256, Kobe, Japan, April 1991. IEEE. Google ScholarDigital Library
- 7.B. Finance and G. Gardarin. A rule-based query optimizer with multiple search strategies. Data and Knowledge Engineering, 13:1-29, 1994. Google ScholarDigital Library
- 8.G. Graefe. The Cascades framework for query optimization. Data Engineering Bulletin, 18(3): 19-29, September 1995.Google Scholar
- 9.G. Graefe and W. J. McKenna. The Volcano optimizer generator:. Extensibility and efficient search. In Proceedings of the Ninth International Conference on Data Engineering, pages 209-218, Vienna, Austria, April 1993. IEEE. Google ScholarDigital Library
- 10.J. Guttag, J. Homing, S. Garland, K. Jones, A. Modet, and J. Wing. Larch: Languages and Tools for Formal Specifications. Springer-Verlag, 1992. Google ScholarDigital Library
- 11.W. Kim. On optimizing an SQL-like nested query. ACM Transactions on Database Systems, 7(3):443-469, September 1982. Google ScholarDigital Library
- 12.J.-S. Lee, K.-E. Kim, and M. Cherniack. A COKO compiler. Available at htrp ://www. cs.brown.edu/softwareJcokokola/coko.tar.Z, 1996.Google Scholar
- 13.G. Mitchell, U. Dayal, and S. B. Zdonik. Control of and extensible query optimizer: A planning-based approach. In Proc. 19th lnt'l Conference on Very Large Data Bases, August 1993. Google ScholarDigital Library
- 14.I, S. Mumick, S. J. Finkelstein, H. Pitahesh, and R. Ramakrishnan. Magic is relevant. In Proc. ACM SIGMOD Int'l Conference on Management of Data, pages 247-258, 1990. Google ScholarDigital Library
- 15.H. Pirahesh, J. M. Heilerstein, and W. Hasan. Extensible/rule based query rewrite optimization in Starburst. In Proc. ACM SIGMOD lnt'l Conference on Management of Data, pages 39-48, San Diego, CA, June 1992. Google ScholarDigital Library
- 16.R. Ramakrishnan. Database Management Systems. McGraw-Hill, 1996. Google ScholarDigital Library
- 17.E. Sciore and J. Sieg Jr. A modular query optimizer generator. In Proceedings of the 6th International Conference on Data Engineering, pages 146-153, Los Angeles, USA, 1990. Google ScholarDigital Library
- 18.P. Seshadri, J. M. Hellerstein, H. Pirahesh, T. C. Leung, R. Ramakrishnan, D. Srivastava, P. J. Stuckey, and S. Sudarshan. Cost-based optimization for magic: Algebra and implementation. In Proc. ACM SIGMOD lnt'l Conference on Management o/Data, Montreal, Qu6bec, Canada, June 1996. Google ScholarDigital Library
Index Terms
- Changing the rules: transformations for rule-based optimizers
Recommendations
Changing the rules: transformations for rule-based optimizers
Rule-based optimizers are extensible because they consist of modifiable sets of rules. For modification to be straightforward, rules must be easily reasoned about (i.e., understood and verified). At the same time, rules must be expressive and efficient (...
Improving efficiency of merging symbolic rules into integrated rules: splitting methods and mergability criteria
Neurules are a type of neuro-symbolic rules integrating neurocomputing and production rules. Each neurule is represented as an adaline unit. Neurules exhibit characteristics such as modularity, naturalness and ability to perform interactive and ...
Dynamic Refinement of Classification Rules
ICTAI '02: Proceedings of the 14th IEEE International Conference on Tools with Artificial IntelligenceGiven a set of training examples in the form of (input, output) pairs, induction generates a set of rules that when applied to an input example, can come up with a target output or class for that example. At deduction time, these rules can be applied to ...
Comments