On the Complexity of Generating Optimal Plans with Cross Products.

Wolfgang Scheufele, Guido Moerkotte: On the Complexity of Generating Optimal Plans with Cross Products. PODS 1997: 238-248

@inproceedings{DBLP:conf/pods/ScheufeleM97,
  author    = {Wolfgang Scheufele and
               Guido Moerkotte},
  title     = {On the Complexity of Generating Optimal Plans with Cross Products},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {238-248},
  ee        = {http://doi.acm.org/10.1145/263661.263687, db/conf/pods/ScheufeleM97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In modern advanced database systems the optimizer is often faced with the problem of finding optimal evaluation strategies for queries involving a large number of joins. Examples are queries generated by deductive database systems and path expressions in object-oriented database systems. The best plan can be found in the very large search space of bushy trees where plans are allowed to contain cross products. A general question arises: For which (sub-) problems can we expect to find polynomial algorithms generating the best plan? We attack this question from both ends of the spectrum. First, we show that we cannot expect to find any polynomial algorithm for any subproblem as long as optimal bushy trees are to be generated. More specifically, we show that the problem is NP-hard independent of the query graph. Second, for the restricted cIass of chain queries, we present two efficient algorithms for the problem of generating left-deep trees possibly containing cross products.

Copyright © 1997 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona. ACM Press 1997, ISBN 0-89791-910-6
Contents

Online Edition: ACM Digital Library

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

References

[1]: Sophie Cluet, Guido Moerkotte: On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products. ICDT 1995: 54-67
[2]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[3]: ...
[4]: Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)
[5]: Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177
[6]: Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137
[7]: ...
[8]: ...
[9]: Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
[10]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[11]: ...
[12]: Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492
[13]: ...
[14]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
[15]: Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46