[theory]DBMS join order optimization - Tilted Forum Project - TFP - Sexuality, Philosophy and Political Discussion

kel · 02-07-2004, 08: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, 11:28 AM

kel · 02-08-2004, 02:37 PM

So no one wants to touch this?
Not even with a 10 foot pole?

cheerios · 02-08-2004, 02:41 PM

not w/ a 50 foot poll. sorry

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

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

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