A Chase Too Far? Lucian Popa, Alin Deutsch, Arnaud Sahuguet, and Val Tannen   View Paper (PDF)   Return to Research Sessions Abstract In a previous paper we proposed a novel method for generating alternative query plans that uses chasing (and back-chasing) with logical constraints. The method brings together use of indexes, use of materialized views, semantic optimization and join elimination (minimization). Each of these techniques is known separately to be beneficial to query optimization. The novelty of our approach is in allowing these techniques to interact systematically, eg. non-trivial use of indexes and materialized views may be enabled only by semantic constraints. We have implemented our method for a variety of schemas and queries. We examine how far we can push the method in term of complexity of both schemas and queries. We propose a technique for reducing the size of the search space by "stratifying" the sets of constraints used in the (back) chase. The experimental results demonstrate that our method is practical (i.e., feasible and worthwhile). References Note: References link to DBLP on the Web. [1] ... [2] Catriel Beeri , Yoram Kornatzky : Algebraic Optimization of Object-Oriented Query Languages. TCS 116(1&2) : 59-94(1993) [3] Randall G. Bello , Karl Dias , Alan Downing , James Feenan Jr. , William D. Norcott , Harry Sun , Andrew Witkowski , Mohamed Ziauddin : Materialized Views in Oracle. VLDB 1998 : 659-664 [4] Upen S. Chakravarthy , John Grant , Jack Minker : Logic-Based Approach to Semantic Query Optimization. TODS 15(2) : 162-207(1990) [5] Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200 [6] Qi Cheng , Jarek Gryz , Fred Koo , T. Y. Cliff Leung , Linqi Liu , Xiaoyan Qian , Berni Schiefer : Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. VLDB 1999 : 687-698 [7] Mitch Cherniack , Stanley B. Zdonik : Inferring Function Semantics to Optimize Queries. VLDB 1998 : 239-250 [8] Sophie Cluet , Claude Delobel : A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992 : 383-392 [9] Alin Deutsch , Lucian Popa , Val Tannen : Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999 : 459-470 [10] Leonidas Fegaras , David Maier : An Algebraic Framework for Physical OODB Design. DBPL 1995 : 9 [11] ... [12] Daniela Florescu , Louiqa Raschid , Patrick Valduriez : A Methodology for Query Reformulation in CIS Using Semantic Knowledge. IJCIS 5(4) : 431-468(1996) [13] John Grant , Jarek Gryz , Jack Minker , Louiqa Raschid : Semantic Query Optimization for Object Databases. ICDE 1997 : 444-453 [14] Matthias Jarke , James Clifford , Yannis Vassiliou : An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984 : 296-306 [15] Alfons Kemper , Guido Moerkotte : Access Support in Object Bases. SIGMOD Conference 1990 : 364-374 [16] ... [17] Greg Nelson , Derek C. Oppen : Fast Decision Algorithms Based on Union and Find. FOCS 1977 : 114-119 [18] ... [19] Lucian Popa , Val Tannen : An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999 : 39-57 [20] Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal 5(2) : 101-118(1996) [21] Patrick Valduriez : Join Indices. TODS 12(2) : 218-246(1987) [22] H. Z. Yang , Per-Åke Larson : Query Transformation for PSJ-Queries. VLDB 1987 : 245-254 BIBTEX @inproceedings{DBLP:conf/sigmod/PopaDST00,   author    = {Lucian Popa and                 Alin Deutsch and                 Arnaud Sahuguet and                 Val Tannen},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {A Chase Too Far?},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {273-284},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.