Part 1    Result Size Estimations (Total:  20 Points)

Consider a table student with attributes CWID, name, major, credits, a table course with title, instructor, credits, and a table registered with attributes student and course. registered .student is a foreign key to CWID. Attribute course of relation registered is a foreign key to attribute title of relation course. Given are the following statistics:

T(student) = 30,000 V(student,CWID) = 30,000 V(student,name) = 29,500

V(student,major) = 20 V(student,credits) = 32

T(course) = 80  V(course,title) = 80 V(course,instructor) = 50

V(course,credits) = 6

T(registered) = 10,000 V(registered,  student) = 3,000

V(registered,  course) = 30

Question 1.1    Estimate Result Size (4 Points)

Estimate the number of result tuples for the query q = σinstructor =BobAcreditss3(course) using the first assump- tion presented in class (values used in queries are uniformly distributed within the active domain). Assume that the minimal and maximal values in the credits attribute are 1 and 6, respectively.

Question 1.2    Estimate Result Size (5 Points)

Estimate the number of result tuples for the query q = σmajor =CSVcredits<10(students) using the first assumption presented in class.   Assume that the minimal and maximal values in the  credits attribute are  1 and 32, respectively.

Question 1.3    Estimate Result Size (5 Points)

Estimate the number of result tuples for the query q = σcredits>3Acreditss5(course) using the first assumption presented in class. Assume that the minimal and maximal values in the credits attribute are 1 and 6.

Question 1.4    Estimate Result Size (6 Points)

Estimate the number of result tuples for the query q below using the first assumption presented in class. Assume that the minimal and maximal values in the credits attribute are 1 and 32,

q = σcredits>20(student) BaCW ID=student registered Bacourse=title  course

Part 2    I/O Cost Estimations (Total:  20 Points)

Question 2.1    I/O Cost Estimation (20 Points)

Consider two unordered,  non-clustered relations  R and  S with B(R)  =  300,000 and B(S)  =  4,000 blocks, and  S(R)  =  ,  and  S(S)  =   .   You have M  =  101 memory pages available.   Let R has an index on the joining attribute C. Compute the minimum number of I/O operations needed to join these two relations using tuple-based-nested-loop join (relations are clustered), block-nested-loop join (relations are unclustered), merge-join  (the inputs are not sorted and non-clustered),  and  non-clustering  index-join  (relations are clustered, read of S with uniform distribution assumption and expected 120 matching tuples on R for S). Justify you result by showing the I/O cost estimation for each join method.