See the file down.

CSCI 6624/4524 — Advanced Databases— 15 Spring HW 4, Due: Thursday, 6/18/15

• This homework is due Thursday, 6/18/15, will be one week late if handed in by 6/25/15, two weeks late if handed in between 6/25/15 and 6/30/15, and will not be accepted after the start of the class on Tuesday, 6/30/15

• Quiz 4 (open book, open notes) will be on Thursday, 6/25/15 and will cover the following topics: Query Processing and Optimization Chapter 19.

• The final exam (open book, open notes) will cover all the material covered in week 1 through week 12; material covered only in student presentations will not be on the final.

• The Extra Credit problems are due Tuesday, 6/23/15 and will not be accepted late.

1. (20 points)

Give brief and clear answers to the following:

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

(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. (45 points)

(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 EMPLOY EE ./SSN=ESSN WORKSON, and we are using J1, the nested-loop join approach. Further suppose that the buffer size nB = 8, the EMPLOY EE file has 8000 records in 1000 blocks, and the WORKSON file has 2000 records in 500 blocks. Calculate the number of disk accesses if

i. EMPLOY EE is the outer relation.

ii. WORKSON 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 ex- pression. 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 inter- mediate steps i.e. you only have to show a final tree similar to Elmasri Figure 19.5 (e), and not the intermediate trees like 19.5 (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(σEMPLOY EE.Sex=‘F ′ (EMPLOY EE ./SSN=ESSN DEPENDENT)).

(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=‘Marketing′ ( (EMPLOY EE ./SSN=ESSN WORKSON) ./Pno=Pnumber (PROJECT ./Dnum=Dnumber DEPARTMENT) ))).

Extra Credit 12: Do some research and find out and explain the difference between how Oracle and SQLServer store files.

Extra Credit 13: Do some research and find out and explain the difference between how Oracle and SQLServer do query optimization.

Extra Credit 14: In the language of your choice write a program to implement the Sort Merge External Sorting algorithm. Turn in a hard copy of the documented source code, and sample runs and turn in the soft copy on blackboard.

2