Your cart is currently empty!
Ex. 1 (7 pts) Consider a disk with average seek time of 10 ms, average rotational latency of 5 ms, and a transfer time of 1 ms for a 4KB block. The cost of reading/writing a block is the sum of these values (i.e. 16 ms). We are asked to sort a large relation…
Ex. 1 (7 pts)
Consider a disk with average seek time of 10 ms, average rotational latency of 5 ms, and a transfer time of 1 ms for a 4KB block. The cost of reading/writing a block is the sum of these values (i.e. 16 ms). We are asked to sort a large relation consisting of 10,000,000 blocks of 4KB each. For this, we use a computer on which the main memory available for buffering is 320 blocks (somewhat small memory). We begin as usual by creating sorted runs of 320 blocks each in phase 1. Then, we do 319-way merges. Determine the number of phases needed, and evaluate the cost of the Multi Phase Multiway Merge Sort.
Ex. 2 (7 pts)
Build a B+ tree index with n=3 using the following sequence of keys:
2, 15, 31, 32, 6, 18, 19, 20, 3, 4, 5, 40, 41, 42
Redraw the tree each time an insertion is done.
Ex. 3 (5 pts)
Consider the following query plan.
What is the cost in terms of number of I/Os for this plan?
Notes. The result of the left selection, being small, is kept in main memory, where it is sorted. The result of the right selection is pipelined to the join operator, i.e. the generation of the sorted sublists for the first phase of sort is done on the fly. Do not count the I/Os for writing the final results (after projection).
Consult queryeval.pdf for the table statistics.
Ex. 4 (12 pts)
For each of the schedules of transactions T1, T2, and T3 below:
do each of the following:
Tell what happens when each schedule is run by a scheduler that supports shared and exclusive locks.
Tell what happens when each schedule is run by a scheduler that supports shared locks, exclusive locks, and upgrading.
Tell what happens when each schedule is run by a scheduler that supports shared, exclusive, and update locks.
Ex 5. (5 pts)
Consider the following sequence of UNDO log records:
<START S>
<S,A,60>
<COMMIT S>
<START T>
<T,A,10>
<START U>
<U,B,20>
<T,C,30>
<START V>
<U,D,40>
<V,F,70>
<COMMIT U>
<T,E,50>
<COMMIT T>
<V,B,80>
<COMMIT V>
Suppose that we begin a nonquiscent checkpoint immediately after one of the following log records has written (in memory):
For each, tell:
Ex 6. (5 pts)
Consider the previous exercise, but interpret the log as a REDO log.
For each (a,b,c,d,f), tell:
Ex. 7. (6 pts)
For each of the following relation schemas and sets of FD’s:
Indicate the BCNF violations (if any). Decompose the relations, as necessary, into relations that are in BCNF.