CS245 PROBLEM SET #5
Due by 5:30pm, Tuesday, August 17, 1999

Problem 1: Interleaving of Transactions (20 points)

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 every serial schedule conflict equivalent to H, T2 precedes T1.
The schedule may include more than 2 transactions and you do not need to consider locking actions. Please use as few transactions and read or write actions as possible.


Problem 2: Undo/Redo Logging and Two Phase Locking (20 points)

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). Assume the log entrys are in the format <Tid, Variable, Old value, New value>. 
        < 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.
(a)
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.

(b)
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 3: Conflict Serializability and Locking Rules (20 points)

(a)
Give a simple schedule where (exactly) one transaction in the schedule is not well formed, and this causes the schedule to be non-conflict-serializable. Show why your schedule is not conflict-serializable.

(b)
Give a simple non-legal schedule that is not conflict-serializable. Show why your schedule is not conflict-serializable.

(c)
Give a simple schedule where (exactly) one transaction in the schedule is not using two phase locking, and that causes the schedule to be non-conflict-serializable. Show why your schedule is not conflict-serializable.

(d)
Give a simple conflict serializable schedule that cannot be produced by a two phase locking scheduler. Show why your schedule is conflict serializable, and why it cannot be produced by a two phase locking scheduler. For this particular question, your example schedule should contain only read and write actions. All the lock and unlock actions are hidden.
Use as few transactions and actions as possible in your examples.


Problem 4: Group Modes in Lock Tables (20 points)

Consider the shared/exclusive/warning scheme described in class and in the lecture notes. In the table below you are given six different cases of simultaneously held locks on some object. In each case, give the group mode that is stored in the lock table, or explain briefly why the situation is impossible.

CaseLocks
(a)S, S, IS
(b)S, IS, SIX
(c)IX, IS, IS
(d)IX, X
(e)SIX, IX
(f)SIX, IS