Assignment #4 Solution

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:




r1(A); r2(B); r3(C); r1(B); r2(C); r3(D); w1(A); w2(B); w3(C);
r1(A); r2(B); r3(C); r1(B); r2(C); r3(A); w1(A); w2(B); w3(C);



do each of the following:




i. Insert shared and exclusive locks, and insert unlock actions. Place a shared lock immediately in front of each read action that is not followed by a write action of the same element by the same transaction. Place an exclusive lock in front of every other read or write action. Place the necessary unlocks at the end of every transaction.




Tell what happens when each schedule is run by a scheduler that supports shared and exclusive locks.




Insert shared and exclusive locks in a way that allows upgrading. Place a shared lock in front of every read, an exclusive lock in front of every write, and place the necessary unlocks at the ends of the transactions.



Tell what happens when each schedule is run by a scheduler that supports shared locks, exclusive locks, and upgrading.




Insert shared, exclusive, and update locks, along with unlock actions. Place a shared lock in front of every read action that is not going to be upgraded, place an update lock in front of every read action that will be upgraded, and place an exclusive lock in front of every write action. Place unlocks at the ends of transactions, as usual.



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):




<S,A,60
<T,A,10
<U,B,20
<U,D,40
<T,E,50



For each, tell:

When the <END CKPT record is written, and



For each possible point at which a crash could occur, how far back in the log we must look to find all the possible incomplete transactions.



Ex 6. (5 pts)

Consider the previous exercise, but interpret the log as a REDO log.




For each (a,b,c,d,f), tell:

At what points could the <END CKPT record be written, and



For each possible point at which a crash could occur, how far back in the log we must look to find all the possible incomplete transactions. Consider both the case that the <END CKPT record was or was not written prior to the crash.



Ex. 7. (6 pts)

For each of the following relation schemas and sets of FD’s:




R(A,B,C,D) with FD’s ABC, BD, CDA, ADB.
R(A,B,C,D) with FD’s AB, BC, CD, DA.



Indicate the BCNF violations (if any). Decompose the relations, as necessary, into relations that are in BCNF.