Chapter 16, Problem 14PE

Explanation of Solution

Explanation:

• The System R optimizer only considers left-deep join, and it is specified in Section 16.4 of the textbook.
• To compute the optimal join order, constant time is required for any pair of subset (say “A” and “B”).
• Subset “A” can denote $\text{k}+1$ different subsets with the size which is exactly equal to “k” for each subset that contains $\text{k}+1$ relations.
• Only a single relation can appear as the right side of the topmost join and this is the reason to consider only “k” size.
• Therefore, the optimal join order is calculated in $\text{k}+1$ time for each subset which has $\text{k}+1$ relations.
• The optimal join order will be calculated for all the $\left(\begin{array}{c}\text{n}\\ \text{k+1}\end{array}\right)$ subsets having size of “k” as,

$\left(\begin{array}{c}\text{n}\\ \text{k}+1\end{array}\right)\text{k}+</$