[theory]DBMS join order optimization - Tilted Forum Project Discussion Community

kel · 02-07-2004, 07:44 AM

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

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

02-07-2004, 10:28 AM	#2 (permalink)
kel WARNING: FLAMMABLE Location: Ask Acetylene	And converted to a .gif __________________ "It better be funny"

02-08-2004, 01:37 PM	#3 (permalink)
kel WARNING: FLAMMABLE Location: Ask Acetylene	So no one wants to touch this? Not even with a 10 foot pole? __________________ "It better be funny"

02-08-2004, 01:41 PM	#4 (permalink)
cheerios Banned Location: 'bout 2 feet from my iMac	not w/ a 50 foot poll. sorry