Find the best join order according to the dynamic programming algorithm used in System-R. You should give the dynamic programming table entries for evaluate the join orders. The cost of each join is the number of I/O accesses the database system performs to execute the join. Assume that the database system uses the two-pass sort-merge join algorithm to perform the join operation. Each block contains 4 tuples and tuples of all relations have the same size. We are interested only in left-deep join trees. Note that you should use the System-R optimizer formula to compute the size of each join output.

 

Transcribed Image Text:

R(A,B,C) S(B,C) T(R)=4000 T(S)=3000 V(R,A)=100 V(R,B)=200 V(S,B) =100 V(R,C) 100 V (S,C) = 300 W(B,D) T(W)=2000 V(W,B) =100 U(A,D) T(U)=1000 V(U,A)=100 V(W,D)=50 V(U,D)=100 R(A,B,C) S(B,C) T(R)=4000 T(S)=3000 V(R,A)=100 V(R,B)=200 V(S,B) =100 V(R,C) 100 V (S,C) = 300 W(B,D) T(W)=2000 V(W,B) =100 U(A,D) T(U)=1000 V(U,A)=100 V(W,D)=50 V(U,D)=100