sigmod_1998_elementary.txt

利用lwp：：get写的

This paper introduces algorithms to recognize the invariant part of a data flow tree, and to restructure the evaluation plan to reuse the stored intermediate result. We also propose an efficient method to teach an existing join optimizer to understand the invariant feature and thus allow it to be able to generate better join plans in the new context. Some other related optimization techniques are also discussed. The proposed techniques were implemented within three months on an existing real commercial database system.
We also experimentally evaluate our proposed technique. Our evaluation indicates that, when query rewriting is not possible, the invariant technique is significantly better than the traditional nested iteration method. Even when query rewriting applies, the invariant technique is sometimes better than the query rewriting technique. Our conclusion is that the invariant technique should be considered as one of the alternatives in evaluating correlated queries since it fills the gap left by rewriting techniques.</abstract></paper><paper><title>Query unnesting in object-oriented databases</title><author><AuthorName>Leonidas Fegaras</AuthorName><institute><InstituteName>Department of Computer Science and Engineering, The University of Texas at Arlington, 416 Yates Street, P.O. Box 19015, Arlington, TX</InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Management of Data</conference><citation><name>Jos&amp;#233; A. Blakeley , William J. McKenna , Goetz Graefe, Experiences building the open OODB query optimizer, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.287-296, May 25-28, 1993, Washington, D.C., United States</name><name>Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994</name><name>Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>R. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1994.</name><name>Mitch Cherniack , Stan Zdonik, Changing the rules: transformations for rule-based optimizers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.61-72, June 01-04, 1998, Seattle, Washington, United States</name><name>M. Cherniack, S. Zdonik, J. Lee, and K. Kim. Composing Rules the COKO-KOLA Way. Brown University, March 1997.</name><name>Jens Clau&amp;#223;en , Alfons Kemper , Guido Moerkotte , Klaus Peithner, Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.286-295, August 25-29, 1997</name><name>S. Cluet and G. Moerkotte. Efficient Evaluation of Aggregates on Bulk Types. Technical report, Aachen University of Technology, October 1995. Technical Report 95-05.</name><name>S. Cluet and G. Moerkotte. Nested Queries in Object Bases. In Fifth International Workshop on Database Programming Languages, Gubbio, Italy, September 1995.</name><name>L. Fegaras. An Experimental Optimizer for OQL. University of Texas at Arlington Technical Report TR- CSE-97-007. Available at http://www-cse.uta.edu/ ~fegaras/oqlopt.ps.gz, May 1997.</name><name>L. Fegaras. Query Unnesting in Object-Oriented Databases (extended version). Available at http ://www-cse. uta. edu/~f egaras/s igmod98, ps, January ]998.</name><name>Leonidas Fegaras , David Maier, An Algebraic Framework for Physical OODB Design, Proceedings of the Fifth International Workshop on Database Programming Languages, p.9, September 06-08, 1995</name><name>Leonidas Fegaras , David Maier, Towards an effective calculus for object query languages, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.47-58, May 22-25, 1995, San Jose, California, United States</name><name>L. Fegaras, D. Maier, and T. Sheard. Specifying Rulebased Query Optimizers in a Reflective Framework. Deductive and Object-Oriented Databases, Phoenix, Arizona, pp 146-168, December 1993. Springer-Verlag, LNCS 461.</name><name>Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States</name><name>Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982</name><name>Jie Lin , Z. Meral Ozsoyoglu, Processing OODB queries by O-Algebra, Proceedings of the fifth international conference on Information and knowledge management, p.134-142, November 12-16, 1996, Rockville, Maryland, United States</name><name>M. Muralikrishna, Improved Unnesting Algorithms for Join Aggregate SQL Queries, Proceedings of the 18th International Conference on Very Large Data Bases, p.91-102, August 23-27, 1992</name><name>S. L. Peyton Jones. The Implementation of Functional Programming Languages. Prentice-Hall, Inc., 1987.</name><name>Hennie J. Steenhagen , Peter M. G. Apers , Henk M. Blanken, Optimization of nested queries in a complex object model, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.337-350, May 1994, Cambridge, United Kingdom</name><name>Phil Trinder, Comprehensions, a query notation for DBPLs, Proceedings of the third international workshop on Database programming languages : bulk types &amp; persistent data: bulk types &amp; persistent data, p.55-68, April 1992, Nafplion, Greece</name><name>P. Trinder and P. Wadler. Improving List Comprehension Database Queries. In in Proceedings of TEN- CON'89, Bombay, India, pp 186-192, November 1989.</name><name>Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France</name><name>Limsoon Wong, Normal forms and conservative properties for query languages over collection types, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-36, May 25-28, 1993, Washington, D.C., United States</name><name>Limsoon Wong , Peter Buneman, Querying nested collections, 1994</name></citation><abstract>There is already a sizable body of proposals on OODB query optimization. One of the most challenging problems in this area is query unnesting, where the embedded query can take any form, including aggregation and universal quantification. Although there is already a number of proposed techniques for query unnesting, most of these techniques are applicable to only few cases. We believe that the lack of a general and simple solution to the query unnesting problem is due to the lack of a uniform algebra that treats all operations (including aggregation and quantification) in the same way.