Consider a disk with average seek time of 10 ms

Question 1 [5 marks] 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 Two-Phase Multiway Merge Sort.
Question 2 [7 marks] Consider a B+ tree index with n = 3.
(a) Insert the following sequence of keys: 2,15,31,32,6,18,19,20,25. Draw the resulting tree. (b) Starting with the tree from the end of part (a), delete 20 and then delete 19. Draw the resulting tree. (c) Starting with the tree from the end of part (b), insert the following sequence of keys: 3,4,40. Draw the resulting tree.
Question 3 [6 marks] We will use the following two relations:
Employees(SIN, ename, rating, address) Maintenances(SIN, planeID, day, type)
Maintenances contains 1000 blocks with 100 tuples/block. Employees contains 50 blocks with 120 tuples/block. Consider the query plan below. The left selection yields 10 blocks and, being small, is kept in main memory, where it is sorted. The result of the right selection is 25 blocks and is then 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).
1
(a) What is the cost in terms of number of I/Os for this plan? (b) Consider the query plan that pushes both selections above the join operator so that they can be computed on the fly. Compare the number of I/Os required for this plan when using nested loops versus sort-merge for the join operator.
Question 4 [12 marks] Consider the two schedules S1 and S2 of transactions T1, T2, and T3 below. • S1: r1(A); r2(B); r3(C); r1(B); r2(C); r3(D); w1(A); w2(B); w3(C); • S2: r1(A); r2(B); r3(C); r1(B); r2(C); r3(A); w1(A); w2(B); w3(C); For both S1 and S2 do each of the following:
(a) 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.
Explain what happens when each schedule is run by a scheduler that supports shared and exclusive locks.
(b) 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.
Explain what happens when each schedule is run by a scheduler that supports shared locks, exclusive locks, and upgrading.
(c) 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.
2
Explain what happens when each schedule is run by a scheduler that supports shared, exclusive, and update locks.
Question 5 [10 marks] 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):
(a) <S,A,60 (b) <T,A,10 (c) <U,B,20 (d) <U,D,40 (e) <T,E,50
For each, indicate (i) When the <END CKPT record is written, and (ii) 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.
Question 6 [10 marks] Consider the previous exercise, but interpret the log as a REDO log. For each (a,b,c,d,f), indicate (i) at what points could the <END CKPT record be written, and (ii) 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.
3