CS245A PROBLEM SET #6
Due by 5pm, Thursday, March 5, 1998.
4 problems, equal credit. 100 pts.

Problem 1:Undo/Redo Logging and 2PL Locking

In this problem, you are given the current contents of the log of a DBMS. The DBMS uses UNDO/REDO logging with non-quiescent checkpoints (with checkpoint starts and checkpoint ends). The log contents are shown below (sequence is ordered left to right, top to bottom, so < T1, start> is the first entry in the sequence and < T3, Z, 40, 80> is the last). 
        < T1, start>              < T1, X, 5, 10>       < T2 start>
        < T2 X, 10, 20>           < T1 commit>          < T2, Y, 30, 60>
        < checkpoint start>       < T2, W, 35, 70>      < T3, start>
        < T3, W, 70, 40>          < checkpoint end>     < T2, Z, 20, 40>
        < T2, commit>             < T3, Z, 40, 80>
You are also given that the concurrency mechanism used by the DBMS is two phase locking, and there are only read and write locks.
  1. Is it possible for the log to have the above contents, given our assumptions about the system? Explain briefly. If the answer is no, which is the first "impossible" log entry? Why? Remove that entry. Is it possible for the log to contain the new sequence? Again explain why or why not. Repeat until you get a possible sequence of log entries.

  2. For the sequence of entries you got in (1), what are the possible values of X,Y,W,Z after the last of these log records is written to disk and before recovery? Briefly explain why.

Problem 2:Conflict Serializability and 2PL

Give a conflict serializable schedule that cannot be produced by a 2 Phase Locking scheduler. Use as few transactions and read or write actions as possible.

Problem 3:Transaction execution order

Solve problem 13.7 in SKS (3rd edition)

Problem 4:Interleaving of Transactions

Two transactions are not interleaved in a schedule if every action of one transaction precedes every action of the other. We say transaction T1 precedes T2 if they are not interleaved, and all actions of T1 precede actions of T2. Give an example of a conflict serializable schedule H that has the following properties:
  1. transactions T1 and T2 are not interleaved in H;
  2. T1 precedes T2 in H; and
  3. in any serial schedule conflict equivalent to H, T2 precedes T1.
The schedule may include more than 2 transactions and you do not need to consider different types of locks. As in Problem 2, use as few transactions and read or write actions as possible.

Last modified: Wed Feb 25 19:32:27 PST 1998