Uniformly-Distributed Random Generation of Join Orders.

@inproceedings{DBLP:conf/icdt/Galindo-LegariaPK95,
  author    = {C{\'e}sar A. Galindo-Legaria and
               Arjan Pellenkoft and
               Martin L. Kersten},
  editor    = {Georg Gottlob and
               Moshe Y. Vardi},
  title     = {Uniformly-Distributed Random Generation of Join Orders},
  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     = {280-293},
  ee        = {db/conf/icdt/Galindo-LegariaPK95.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

[BFMY83]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX

[CP85]

Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX

[GLPK94]

César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95 BibTeX

[GLW82]

Udai Gupta, D. T. Lee, C. K. Wong: Ranking and Unranking of 2-3 Trees. SIAM J. Comput. 11(3): 582-590(1982) BibTeX

[Gra93]

Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX

[HP73]

...

[IK90]

Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 BibTeX

[IK91]

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 BibTeX

[Kan91]

Younkyung Cha Kang: Randomized Algorithms for Query Optimization. Ph.D. thesis, Univ. of Wisconsin-Madison 1991
BibTeX

[Knu68]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[KRB85]

Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents BibTeX

[LVZ93]

Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504 BibTeX

[OL90]

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

[RH77]

Frank Ruskey, T. C. Hu: Generating Binary Trees Lexicographically. SIAM J. Comput. 6(4): 745-758(1977) BibTeX

[SG88]

Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 BibTeX

[Swa89a]

Arun N. Swami: Optimization of Large Join Queries. Ph.D. thesis, Stanford University, Department of Computer Science 1989
BibTeX

[Swa89b]

Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX

[Swa91]

...

[Ull82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[VF90]

Jeffrey Scott Vitter, Philippe Flajolet: Average-Case Analysis of Algorithms and Data Structures. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 431-524 BibTeX

[vL90]

Jan van Leeuwen: Graph Algorithms. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 525-631 BibTeX

Referenced by

1. Florian Waas, César A. Galindo-Legaria: Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer. SIGMOD Conference 2000: 499-509
2. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315
3. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: Duplicate-Free Generation of Alternatives in Transformation-Based Optimizers. DASFAA 1997: 117-124