1. [25 pts] Draw the B+ tree with order d = 2, (that is, each node except the root must contain no fewer than 2 and no more than 4 entries) that results from inserting keys 1, 2, 3, ... 14 in that order and following the split rules used in the book. Show only the final tree.
2. [25 pts] Draw the extensible hash structure that would result from inserting the keys from Question 1 assuming each bucket can hold at most three (3) keys. Start by using a structure with global depth = 1 (i.e., two buckets). As in question 1 show only the final state. Be sure to indicate the global and all local depths, as well as the directory and all pointers. Be sure to use the low order bits of the key's binary representations.
3. [20 pts] Consider the following transactions:
T1: R(A), W(A), R(B), W(B), Commit.
T2: R(C), R(A), W(C), Commit.
T3: R(B), W(B), R(C), W(C), Commit.
Show a serializable schedule of the operations of the above transactions that is NOT a serial schedule and in which at some point, all three transactions are active (i.e., they have performed at least one operation, but not yet commited) simultaneously. Your schedule should be able to be produced using Strict Two-Phase Locking (i.e., all locks held until the end of the transaction). Your should (obviously) not deadlock. Be sure to indicate which transaction is performing each operation and how the operations are interleaved.
For questions 4-6, consider the execution of the ARIES recovery algorithm given the following log (assume a checkpoint is completed before LSN 0 and the Dirty Page Table (DPT) and Transaction Tables for that checkpoint are empty):
LSN | Log Record |
10 | Update: T1 writes P1 |
20 | Update: T2 writes P3 |
30 | T1 abort |
40 | Update: T3 writes P4 |
50 | Update: T2 writes P2 |
60 | T2 commit |
70 | Update: T3 writes P2 |
80 | T2 end |
X - crash, restart |
4. [10 pts] During Analysis: a) What log records are read? b) What are the contents of the Dirty Page Table (DPT) and the transaction table at the end of the analysis stage?
5. [10 pts] During Redo: a) What log records are read? b) What data pages are read? c) What operations are redone (assuming no updates made it out to disk before the crash)? d) Show any new log records that are written.
6. [10 pts] During Undo: a) What log records are read? b) What operations are undone? c) Show any new log records that are written (for CLRs, be sure to show the undoNextLSN)?