Chapter 16, Problem 13PE

Explanation of Solution

Computation time of lowest-cost join order:

• The algorithm for join order optimization is given in Figure 16.7 of the textbook.
• From the join order optimization algorithm, to compute optimal join order, a constant time is required for any pair of subset say “A” and “B”.
• Subset “A” can denote 2^k+1–2 different subsets with the size less than or equal to “k” for each subset that contains k+1 relations.
• The optimal join order is calculated in 2^k+1 time for each subset that contains k+1 relations.
• The optimal join order is calculated in $\left(\frac{\text{n}}{\text{k}+1}\right)2^{\text{k}+1}$ time for all the subsets that contains $\left(\frac{\text{n}}{\text{k}+1}\right)$ relations