||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
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.
- 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.
- 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
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:
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.
- transactions T1 and T2 are not interleaved in H;
- T1 precedes T2 in H; and
- in any serial schedule conflict equivalent to H, T2 precedes T1.
Last modified: Wed Feb 25 19:32:27 PST 1998