1. Give brief and clear answers to the following:

(a) Explain the main advantage B-trees have over a multilevel index of the type.

(b) Since indexes speed up searches, why wouldn't the DBMS automatically create an index for every column of a table?

(c) A file of 16000 blocks is to be sorted with an available buffer space of 16 blocks. How many passes will be needed in the merge phase of the external sort-merge algorithm ?
2.  (a) Suppose the relation R has an attribute A with the following 17 records:

34, 5, 24, 32, 25, 28, 3, 26, 31, 18, 32, 14, 13, 19, 3, 2, 7 Show how the sort-merge external sorting algorithm will sort these values, by showing
i. what the initial sorted runs will look like.
ii. what the runs will look like after each merge pass
iii. what the final sorted file will look like (split into blocks).

Please note that you do not have to show any further calculations, just show what the file blocks look like for each of the above.

You can assume that each block can store 2 records, and that the number of buffer blocks available is nB = 3

(b) Suppose the operation is EMP LOY EE ./SSN=ESSN W ORKSON, and we are using J1, the nested-loop join approach. Further suppose that the buffer size nB = 8, the EMP LOY EE file has 8000 records in 1000 blocks, and the W ORKSON file has 2000
records in 500 blocks. Calculate the number of disk accesses if

i. EMP LOY EE is the outer relation.
ii. W ORKSON is the outer relation.

(c) There are two relations R(A,B) and S(B,C), and the operation is R ./B=B S, and we are using J2, the single-loop join approach. The R file has 2000 records in 100 blocks. The S file has 100 records in 10 blocks. Assume the relationship between R and S is 1-1 and partial-total i.e. for every R tuple, there is at most one S tuple, and for every S tuple, there is exactly one R tuple. For R, there is a secondary index on the field B. For S, there is a secondary index on the field B. The index levels are χR = 7, χS = 3. Calculate the number of disk accesses if

i. R is the outer relation and we use J2.
ii. S is the outer relation and we use J2.

3. (35 points) For each of these queries based on the Elmasri company database, do the following

i Show the initial query tree which is a direct translation of the given relational algebra expression. Please note that your tree should be similar to the tree in Figure 19.4 (a), and not the canonical tree in Figure 19.4 (b).
ii Show the final, more efficient query tree you will get after you have applied the different transformations. Please note that you just have to show the final tree and not the intermediate steps i.e. you only have to show a final tree similar to Elmasri , and not the intermediate trees like (c), (d). You should try and get the most efficient tree you can.

(a) Get the names of the dependents of female employees. The initial relational algebra expression is: πDependentName(σEMP LOY EE.Sex=‘F0(EMP LOY EE ./SSN=ESSN DEP ENDENT)).

(b) Find the last names of employees whose salary is less than 40,000 and who work on a projects controlled by the Marketing department. The initial relational algebra expression is: πLName(σSalary<40,000(σDname=‘Marketing0( (EMP LOY EE ./SSN=ESSN W ORKSON) ./P no=P number (P ROJECT ./Dnum=Dnumber DEP ARTMENT) ))).