| Database System Implementation |
|
| Database System Implementation |
The total number of serial orders is thus 402.
T3 -----> T2 -----> T1
ii. The schedule is thus conflict-serializable.
iii. The only conflict-equivalent serial schedule is (T_3, T_2, T_1).
We must then consider how the read and write actions interleave with the locks and unlocks. To be consistent, r_1(A) must appear after l_1(A) and before u_1(A), while w_1(B) appears between l_1(B) and u_1(B).
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, non-two-phase-locked 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 two-phase-locked 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 shared-lock 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 shared-lock 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 read-timestamp 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 read-timestamp 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 write-sets of T_3 must be compared with the write-set 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 read-set of T_2 with the write-sets 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.