Intensional Query Optimization

Parke Godfrey and Jarek Gryz

The complete paper is available in PostScript. The full version of the paper (which will appear in JIIS) is also available.

Abstract

We have introduced a new query optimization framework called intensional query optimization (IQO), which enables existing optimization techniques to be applied to queries that use views. In particular, we consider that view definitions may employ unions. Advanced database technologies and applications--such as federation and mediation over heterogeneous database sources--lead to such complex view definitions, and to the need to handle complex, expensive queries.

Query rewriting techniques have been proposed which exploit semantic query caches, materialized views, and semantic knowledge about the database domain to optimize query evaluation. These can augment syntactic optimization to reduce evaluation costs further. Such techniques include semantic query caching, query folding, and semantic query optimization. However, most proposed rewrite techniques ignore views in queries; that is, the views are considered as other tables. The IQO framework enables rewrites to be applied to various expansions of the query, even when no such rewrite is applicable directly to the query itself. With IQO, we optimize the query tree, not just the query.

The IQO framework introduces the notion of a discounted query, which is a query with some of its expansions "separated out", so the query can be recast into pieces that can be optimized. For this approach to be effective, the sum of the costs of evaluating each piece must be less than the cost of evaluating the query itself. This includes the discounted query. We develop an evaluation plan for discounted queries that is generally more efficient than the evaluation of the queries themselves.

Bibliography

  1. U. S. Chakravarthy, John Grant, and Jack Minker. Logic based approach to semantic query optimization. ACM Transactions on Database Systems, 15(2):162-207, June 1990.
  2. C. M. Chen and N. Roussopoulos. The implementation and performance evaluation of the ADMS query optimizer: Integrating query result caching and matching. In Proc. of the 4^th International Conference on Extending Database Technology, Cambridge, UK, 1994.
  3. [paper] Shaul Dar, Michael Franklin, Bjorn Jonsson, Divesh Srivastava, and Michael Tan. Semantic data caching and replacement. In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB), Bombay, India, September 1996. To appear.
  4. Terry Gaasterland, Parke Godfrey, and Jack Minker. An overview of cooperative answering. Journal of Intelligent Information Systems, 1(2):123-157, 1992. Invited paper.
  5. [paper] Terry Gaasterland, Parke Godfrey, and Jack Minker. An overview of cooperative answering. Studies in Logic and Computation 3, chapter 1, pages 1-40. Clarendon Press, Oxford, 1994. Appears orginally as [GGM92:survey].
  6. [paper] Terry Gaasterland, Parke Godfrey, Jack Minker, and Lev Novik. A cooperative answering system. In Andrei Voronkov, editor, Proceedings of the Logic Programming and Automated Reasoning Conference, Lecture Notes in Artificial Intelligence 624, pages 478-480. Springer-Verlag, St. Petersburg, Russia, July 1992.
  7. Annie Gal and Jack Minker. Informative and cooperative answers in databases using integrity constraints. pages 277-300. North Holland, 1988.
  8. [paper] Parke Godfrey and Jarek Gryz. A framework for intensional query optimization. In Forca Giannotti Dimitri Boulanger, Ultrich Geske and Dietmar Seipel, editors, Proceedings of the Workshop on Deductive Databases and Logic Programming, held in conjunction with the Joint International Conference and Symposium on Logic Programming (JICSLP'96), GMD-Studien Nr. 295, pages 57-68, Bonn, Germany, September 1996. GMD-Forschungszentrum.
  9. [paper] Parke Godfrey, Jarek Gryz, and Jack Minker. Semantic query optimization for bottom-up evaluation. In Zbigniew W. Ras and Maciek Michalewicz, editors, Foundations of Intelligent Systems: Proceedings of the 9th International Symposium on Methodologies for Intelligent Systems, Lecture Notes in Artificial Intelligence 1079, pages 561-571, Berlin, June 1996. Springer.
  10. [paper] Parke Godfrey, Jack Minker, and Lev Novik. An architecture for a cooperative database system. In Witold Litwin and Tore Risch, editors, Proceedings of the First International Conference on Applications of Databases, Lecture Notes in Computer Science 819, pages 3-24. Springer Verlag, Vadstena, Sweden, June 1994.
  11. John Grant and Jack Minker. On optimizing the evaluation of a set of expressions. International Journal of Computer and Information Sciences, 11:179-191, 1982.
  12. [paper] Arthur M. Keller and Julie Basu. A predicate-based caching scheme for client-server database architectures. The VLDB Journal, 5(2):35-47, April 1996.
  13. S. Lee, L.J.Henschen, and G.Z. Qadah. Semantic query reformulation in deductive databases. In Proc. IEEE International Conference on Data Engineering, pages 232-239. IEEE Computer Society Press, 1991.
  14. A. Y. Levy, A. Rajaraman, and J.J. Ordille. Querying heterogeneous information sources using source descriptions. In Proc. 22nd VLDB, 1996.
  15. A. Y. Levy and Y. Sagiv. Semantic query optimization in datalog programs. In Proceedings of Principles of Database Systems, 1995.
  16. [paper] Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering queries using views. In Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Princliples of Data Systems. ACM, May 1995. To appear.
  17. John W. Lloyd. Foundations of Logic Programming. Symbolic Computation---Artificial Intelligence. Springer-Verlag, Berlin, second edition, 1987.
  18. [paper] Xiaolei Qian. Query folding. In Proceedings of the 12th International Conference on Data Engineering, pages 48-55, 1996.
  19. T. Sellis and S. Shosh. On the multiple-query optimization problem. IEEE Transactions on Knowledge and Data Engineering, 2(2), June 1990.
  20. S. T. Shenoy and Z. M. Ozsoyoglu. Design and implementation of a semantic query optimizer. IEEE Transactions on Knowledge and Data Engineering, 1(3):344-361, September 1989.
  21. Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, Volumes I \& II. Principles of Computer Science Series. Computer Science Press, Incorporated, Rockville, Maryland, 1988.