COS 425, Fall 2004 - Problem Set 6

Due at 1:30pm, Wed. Dec 1, 2004.
Note this is an extension from the due date of Nov 29 originally posted on the schedule page.

Collaboration Policy

You may discuss problems with other students in the class. However, each student must write up his or her own solution to each problem independently. That is, while you may formulate the solutions to problems in collaboration with classmates, you must be able to articulate the solutions on your own.

1. In Database Management Systems by Ramakrishnan and Gehrke, Chapter 17, pg. 575:
Part a: Part 1 of Exercise 17.4: "strict 2PL with timestamps used for deadlock prevention." Assume the wait-die policy is in use.
Part b: Repeat Part 1 of Exercise 17.4 but with the wound-wait policy.
Part c: Part 2 of Exercise 17.4.

2. In Database Management Systems by Ramakrishnan and Gehrke, Chapter 17, pg. 576, Exercise 17.6, but only do:
Part a: An example schedule for region S4.
Part b: An example schedule for region S9.
Part c: An example schedule for region S11.

3. In Database Management Systems by Ramakrishnan and Gehrke, Chapter 18, pg. 599-600, Exercise 18.4.

4. Consider the following execution log: 

LSN    log entry
0      T1 update Pg1  - prevLSN=null
1      T2 update Pg2  - prevLSN=null
2      begin checkpoint
3      end checkpoint
4      T3 update Pg3 - prevLSN=null
5      T1 update Pg4 - prevLSN=0
6      T3 update Pg5 - prevLSN=4
7      T1 commit - prevLSN=5
8      T1 end - prevLSN=7
9      T2 commit - prevLSN=1
Part a: Fill in the contents of the transaction table and the dirty page table saved at the checkpoint.

Part b: Suppose a crash occurs after LSN 9 and again during crash recovery after the first CLR record is written. Describe the actions of the crash recovery phases and show any additions to the log, including undoNextLSN values.