## CPS 432/562 Homework #2

Coverage: [DBCB] Chapter 16, § 16.4, pp. 821-834; and § 16.6, pp. 847-858
Assigned: February 3
Due: February 8, 4:30p, in class

1. (15+15=30 points) Exercise 16.6.1 (parts a and b) on p. 858 from [DBCB]: For the following relations, give the dynamic-programming table entries that evaluates all possible join orders allowing: a) all trees and b) left-deep trees only. What is the best choice in each case?

 W(a,b) X(b,c) Y(c,d) Z(d,e) T(W)=100 T(X)=200 T(Y)=300 T(Z)=400 V(W,a)=20 V(X,b)=50 V(Y,c)=50 V(Z,d)=40 V(W,b)=60 V(X,c)=100 V(Y,d)=50 V(Z,e)=100

2. (5+5=10 points) Exercise 16.6.5 (part b) on p. 859 from [DBCB]. How many trees are there for the join of eight relations? How many of these are neither left-deep not right-deep?

3. (10 points) Show clearly that, with n relations, there are (2(n-1))!/(n-1)! different join orders. Use the fact that the number of different complete binary trees with n leaf nodes is C(2(n-1), n-1)/n, where C(n,r) is the number of r-combinations of a set with n elements, i.e., `n choose r.' A complete binary tree is one where every internal node has exactly two children.

4. (2+2+6=10 points) Required only for CPS 562 students
Exercises 5.2.10 on p. 213 and 16.4.3 on p. 835 from [DBCB]: The semi-join of relations R(A,B) and S(B,C), is the bag of tuples in R that agree with at least one tuple in S on all join attributes. An expression in relational algebra that is equivalent to `R semi-join S' is (R S), where L represents the set of all attributes in R. Give two additional expressions in relational algebra which are equivalent to `R semi-join S.' Each of these additional expressions must be truly different and not just a rewrite of the given expression or of each other. Now explain how you would estimate the size of a semi-join, using the ideas presented in class for estimating the size of natural joins?