Tilted Forum Project Discussion Community

Tilted Forum Project Discussion Community (https://thetfp.com/tfp/)
-   Tilted Technology (https://thetfp.com/tfp/tilted-technology/)
-   -   [theory]DBMS join order optimization (https://thetfp.com/tfp/tilted-technology/44731-theory-dbms-join-order-optimization.html)

kel 02-07-2004 07:44 AM
[THEORY]DBMS join order optimization
 
So I have been mulling over this question from a problem set for the past week.

Quote:
Show that the lowest-cost join order can be computed in time O(3^n). Assume that you can store and look up information about a set of relations (such as the optimal join order for the set, and the cost of that join order) in constant time. The proof will require the use of a binomial theorem.
(I will format it in PDF and post it here).

The pseudocode for the algorithm used in optimization is also in the PDF which I will post in 10 minutes.

[EDIT] OKAY, here it is. The binomial theorem and the pseudocode for the join order optimization algorithm.[/EDIT]

kel 02-07-2004 10:28 AM
And converted to a .gif
 
http://people.brandeis.edu/~adweisbe/tmp1.gif

kel 02-08-2004 01:37 PM
So no one wants to touch this?
Not even with a 10 foot pole?

cheerios 02-08-2004 01:41 PM
not w/ a 50 foot poll. sorry ;)


All times are GMT -8. The time now is 05:10 PM.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Search Engine Optimization by vBSEO 3.6.0 PL2
© 2002-2012 Tilted Forum Project


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73