CPS 432/562 Homework #2

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?