PART C: External Sorting (13 points)

  Consider a disk with an average seek time of 10ms, average rotational delay of 5ms, and a transfer time of 1ms for a 4K page. Assume that the cost of reading/writing a page is the sum of these values (i.e., 16ms) unless a sequence of pages is read/written. In this case the cost is the average seek time plus the average rotational delay (to find the first page in the sequence) plus 1ms per page (to transfer data). You are given 320 buffer pages and asked to sort a file with 10,000,000 pages.

C.2) Compute the total cost of the following merge sort: In the first pass, I create sorted runs of 320 each. In subsequent merging passes, I create 16 input buffers of 16 pages each, and one output buffer of 64 pages each. Thus this will be a 16-way merge, but I always read 16 pages at a time and I write 64 pages at a time. (7 points)

Let N=10,000,000.

The first pass costs (N/320)*(10+5+1 + 319).

Each subsequent pass costs (N/16)*(10+5+1 + 15) + (N/64)*(10+5+1 + 63)

To calculate the number of passes, use the usual log-formula (note that we are doing a 16-way merge).

E.1) Consider a relation with five attributes ABCDE with the following functional dependencies:
A à BC, CD à E, B à D, E à A

  We decompose ABCDE into the two relations ABC and ADE. Is this decomposition a lossless join decomposition? Is this decomposition a dependency-preserving decomposition? Give (short and precise) reasons for your answers. (6 points)

a) It is lossless join, becase A is a key for ABC

b) Is it not dependency preserving. For example, B à D is not preserved.

E.2) Consider a relation R with five attributes ABCDE. You are given the following functional dependencies:

A à B, BC à E, ED à A

Find all the keys for the relation. In what normal form is relation R? (6 points)

The keys are ACD, BCD, and CDE. The relation is in 3NF.