College of Engineering, Department of EECS, Computer Science Division
CS186, Fall 2002
Homework 6: Index Structures and Transactions
(to be done individually)

Due Date: Monday December 9, 2001 at 5 pm
Last allowed hand in: Tuesday 12/10 5pm (i.e., you can use at most one slip day if you have one) 


1. This homework assignment is to be done individually (i.e., NOT with the project groups).
2. The assignment can be handwritten, but must be legible. No credit will be given for answers that are not easily readable.
3. The assignment should be turned in by depositing it in the CS 186 box on the 2nd Floor of Soda Hall.
4. Note: because we need to present answers prior to the final, we will not accept any late submissions after Tuesday 12/10 at 5pm.


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