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]