Chapter 16, Problem 12PE

Explanation of Solution

Proof:

• Let the number of join orders will be,

$\begin{array}{ccc}\text{Number}\text{of}\text{join}\text{orders}& =& \frac{(2\text{n}-2)!}{(\text{n}-1)!}\end{array}$

• A complete binary tree consists of several internal nodes and each internal node contains exactly 2 children.
• Each join order is considered as a complete binary tree and in which all the relations are considered as the leaves.
• There is a bijection between the count of binary tress of “n-1” nodes and count of binary trees of “n” leaves when considering a database with “n” relations (leaf nodes).
• Hence, the total number of created binary trees are,

$\begin{array}{ccc}\text{Number}\text{of}\text{complete}\text{binary}\text{trees}& =& \frac{1}{\text{n}}\left(\frac{2(\text{n}-1)}{(\text{n}-1)}\right)\end{array}$

• Each complete binary tree of “n” leaves will contain “n-1” nodes.
• Conversely, add “n” leaves to the binary tree to make this tree to a complete binary tree.
• The number of binary trees that contains “n-1” nodes is,

$\begin{array}{ccc}\text{Number}\text{of}\text{complete}\text{binary}\text{trees}& =& \frac{1}{\text{n}}(\frac{2(\text{n}-1}{}\end{array}$