On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products.

@inproceedings{DBLP:conf/icdt/CluetM95,
  author    = {Sophie Cluet and
               Guido Moerkotte},
  editor    = {Georg Gottlob and
               Moshe Y. Vardi},
  title     = {On the Complexity of Generating Optimal Left-Deep Processing
               Trees with Cross Products},
  booktitle = {Database Theory - ICDT'95, 5th International Conference, Prague,
               Czech Republic, January 11-13, 1995, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {893},
  year      = {1995},
  isbn      = {3-540-58907-4},
  pages     = {54-67},
  ee        = {db/conf/icdt/CluetM95.html},
  crossref  = {DBLP:conf/icdt/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 or /cdrom

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

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
BibTeX

[2]

Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX

[3]

Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX

[4]

...

[5]

Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325 BibTeX

[6]

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 BibTeX

Referenced by

1. Wolfgang Scheufele: Review - On the Optimal Nesting Order for Computing N-Relational Joins. ACM SIGMOD Digital Review 2: (2000)
2. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
3. Wolfgang Scheufele, Guido Moerkotte: On the Complexity of Generating Optimal Plans with Cross Products. PODS 1997: 238-248
4. Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46