
Solutions for Section 18.1
Solutions for Section 18.2
Solutions for Section 18.3
Solutions for Section 18.4
Solutions for Section 18.5
Solutions for Section 18.6
Solutions for Section 18.7
Solutions for Section 18.8
Solutions for Section 18.9
The total number of serial orders is thus 402.
i. The precedence graph is
T3 > T2 > T1
ii. The schedule is thus conflictserializable. The only conflictequivalent serial schedule is (T_{3}, T_{2}, T_{1}).
iii. No. Assume, for example, that initially each of A, B, and C are 10. T_{1} sets A and C to 20, T_{2} sets B to A+B+C, and T_{3} prints B. Then if T_{3} does not precede T_{2}, it prints the wrong value, and if T_{2} does not precede T_{1}, it sets B to the wrong value.
The number of these interleavings is (6 choose 3) = 20. Note that 20 is thus the sum of the first two quantities we need to compute; (i) + (ii).
Now, let us count (ii), the number of consistent, nontwophaselocked sequences. The only way a consistent sequence is not 2PL is if the unlock at the end of subsequence (1) or (2) above precedes the lock at the beginning of the other subsequence. There are only 2 ways to interleave (1) and (2) so that all of one goes in front of all of the other (put either subsequence first). Thus, (ii) = 2, so (i) = 20  2 = 18.
Next, let us count the number of twophaselocked sequences, which is (i) + (iii). If the sequence is 2PL, then the two locks precede the two unlocks. We can thus pick one of two orders for the locks and one of two orders for the unlocks, for a total of 4 orders of the lock and unlock actions. The r_{1}(A) action can go anywhere. That is, we can choose any of 5 positions in which to insert the read action among the lock and unlock actions, ranging from before all to after all. Having placed the read action, the w_{1}(B) action can now be placed in any of 6 positions among the other five. The total number of 2PL sequences is thus 4*5*6 = 120.
Since (i) + (iii) = 120, and we already know (i) = 18, we deduce that (iii) = 102.
The last step is to compute the total number of sequences, which is the sum of all four categories. The number of sequences of six actions is 6! = 720. As the number of sequences in the first three categories is 18, 2, and 102, respectively, (iv) = 720  18 2  102 = 598.
(ii): The first three locks and reads are allowed. However, T_{1} cannot get a shared lock on B, nor can T_{2} get a shared lock on C. When T_{3} requests a shared lock on D it is granted. Thus, T_{3} can proceed and eventually unlocks C and D.
As soon as C is unlocked, T_{2} can get its shared lock on C. Thus, T_{2} completes and releases its locks. As soon as its lock on B is released, T_{1} can get its lock on A, so it completes.
(iii): sl_{1}(A); r_{1}(A); sl_{2}(B); r_{2}(B); sl_{3}(C); r_{3}(C); sl_{1}(B); r_{1}(B); sl_{2}(C); r_{2}(C); sl_{3}(D); r_{3}(D); xl_{1}(A); w_{1}(A); u_{1}(A); u_{1}(B); xl_{2}(B); w_{2}(B); u_{2}(B); u_{2}(C); xl_{3}(C); w_{3}(C); u_{3}(C); u_{3}(D)
(iv): First, all six sharedlock requests are granted. When T_{1} requests an exclusive lock on A, it gets it, because it is the only transaction holding a lock on A. T_{1} completes and releases its locks. Thus, when T_{2} asks for an exclusive lock on B, it is the only transaction still holding a shared lock on B, so that lock too may be granted, and T_{2} completes. After T_{2} releases its locks, T_{3} is able to upgrade its shared lock on C to exclusive, and it too proceeds. The actions are thus executed in exactly the same order as they are requested; i.e., there are no delays by the scheduler.
(v): ul_{1}(A); r_{1}(A); ul_{2}(B); r_{2}(B); ul_{3}(C); r_{3}(C); sl_{1}(B); r_{1}(B); sl_{2}(C); r_{2}(C); sl_{3}(D); r_{3}(D); xl_{1}(A); w_{1}(A); u_{1}(A); u_{1}(B); xl_{2}(B); w_{2}(B); u_{2}(B); u_{2}(C); xl_{3}(C); w_{3}(C); u_{3}(C); u_{3}(D)
(vi): The update locks prevent the fourth and fifth sharedlock requests, sl_{1}(B) and sl_{2}(C), so T_{1} and T_{2} are delayed, while T_{3} is allowed to proceed. The situation is exactly as for part (ii), where the initial lock requests are for exclusive locks.
Also, inc_{1}(B) must come before r_{2}(B), so the former can either be the fourth action of the schedule, or it can be fifth, coming after r_{2}(A). Thus, there are two serializable schedules equivalent to (T_{1}, T_{2}), and four serializable schedules altogether.
For example, consider the actions (set angle = 90)(set x = 5) applied to the vector (10,0). The first step gives us (0,10), and the second step gives us (5,10).
On the other hand, the reverse order of the actions: (set x = 5)(set angle = 90) starting with (10,0) gives us (0,5), and the second step gives us (5,5).
Thus, the only needed lock modes are exclusive, shared, and increment, which correctly sum up the limitations on access to a given element in the above three situations, respectively.
At step 2, T_{2} puts an IX lock on the extent and on block 1, both of which are compatible with the IS locks already there. T_{2} also puts an X lock on O_{2}.
At step 3, T_{2} puts an IS lock on the extent and on block 2 and an S lock on O_{3}, then releases its locks.
At step 4, T_{1} puts an IX lock on the extent and on block 2 and an X lock on O_{4}, then releases its locks.
We are then directed to the second leaf. Since that leaf is not full either, we know the insertion will not cause the left child of the root to be changed, so we can release the exclusive lock on that child. As soon as we have rewritten the second leaf to reflect the insertion of 10, we can release the lock on the leaf.
Suppose that T_{1} locks A first. Then T_{2} cannot perform any steps until T_{1} relinquishes the lock. Therefore, T_{1} must also read B, at the second step of the schedule. Now, T_{1} can relinquish the lock on A. The remaining step of T_{1}, r_{1}(E), can occur either before all of T_{2}, or after the first or second step of T_{2}. It cannot occur after the last step of T_{2}, r_{2}(B), because T_{1} can't relinquish its lock on B, until it has locked E. Thus, there are three interleavings in which T_{1} starts first.
Now, consider what happens if T_{2} starts first. T_{2} cannot relinquish its lock on A until it has locked both children B and C. Thus, if T_{2} starts first, it must finish before T_{1} starts. We conclude that there are four legal schedules.
When T_{2} tries to write A, it finds the readtimestamp to be less than the timestamp of T_{2}, so the write may be performed, and T_{2} can commit. However, when T_{1} tries to write B, it finds the readtimestamp is greater than its own timestamp, so some transaction read another value of B, when it should have read T_{1}'s value. Thus, T_{1} must abort.
When T_{4} tries to read A the system finds that T_{4}'s timestamp is larger than that of any version of A written. Thus, T_{4} gets the version with the largest of the timestamps, the one written by T_{3}. That makes sense, because in the hypothetical serial order based on the timestamps of the transactions, T_{3} would be the last to write A.
T_{3} validates next. The only other validated transaction is T_{1}, and T_{1} has not yet finished. Thus, both the read and writesets of T_{3} must be compared with the writeset of T_{1}. However, T_{1} writes only A, and T_{3} neither reads nor writes A, so T_{3}'s validation succeeds.
Last, T_{2} validates. Both T_{1} and T_{3} finish after T_{2} started, so we must compare the readset of T_{2} with the writesets of both T_{1} and T_{3}. Since B is in both W_{3} and R_{2}, we cannot validate T_{2}. Note that since T_{3} (but not T_{1}) finishes after T_{2} validates, we would also compare the write set of T_{2} with the write set of T_{3}, had we not already found a reason not to validate T_{2}.