You may discuss problems with other students in the class. However, each student must write up his or her own solution to each problem independently. That is, while you may formulate the solutions to problems in collaboration with classmates, you must be able to articulate the solutions on your own.
1.In Database Management Systems by Ramakrishnan and Gehrke,
Chapter 14,
Part a: Exercise 14.4, pg. 476, Part 2.
Part b: Exercise 14.4, pg. 476, Part 3.
Part c: Exercise 14.4, pg. 476, Part 4.
Part d: Exercise 14.4, pg. 476, but
add an Alternative 2 hash index on
attribute b of S.
What is the cost of
joining R and S using an index nested loop join?
Part e: Exercise 14.4, pg. 476, but
add an Alternative 1, clustered
B+ tree index of order 50 on attribute a of R.
Assume only this index, not the index of Part d.
What is the cost of
joining R and S using an index nested loop join?
2.Assume that you have relations R and S of Problem 1 above, with the same characteristics and BOTH indexes of Parts d and e. Assume that you also have a relation T with the same properties as relation R, but with no indexes built for it. Also assume that the B+ tree on attribute a of R contains 1000 distinct key values and attribute c of T ranges over 3000 values.
Execute the dynamic programming algorithm to find an optimal left-deep plan
for the evaluation of
((R JOIN S on R.a=S.b) JOIN T on S.b=T.c)
Show your work!