Two transactions \(T_1\) and \(T_2\) are given as…
2017
Two transactions \(T_1\) and \(T_2\) are given as
\(T_1:r_1(X)w_1(X)r_1(Y)w_1(Y)\)
\(T_2:r_2(Y)w_2(Y)r_2(Z)w_2(Z)\)
where \(r_i(V)\) denotes a read operation by transaction \(T_i\) on a variable \(V\) and \(w_i(V)\) denotes a write operation by transaction \(T_i\) on a variable \(V\). The total number of conflict serializable schedules that can be formed by \(T_1\) and \(T_2\) is ______
Attempted by 132 students.
Show answer & explanation
Correct answer: 54
Answer: 54
Explanation (concise):
Total interleavings of the 8 operations (4 from each transaction) = C(8,4) = 70.
Schedules conflict-equivalent to running T1 then T2: because both T1's reads/writes on Y must come before T2's reads/writes on Y, all T2 operations must occur after T1's r1(Y) and w1(Y). That forces the entire T1 to appear before T2, giving exactly 1 such schedule (the serial T1→T2).
Schedules conflict-equivalent to running T2 then T1: we require T2's r2(Y) and w2(Y) to appear before T1's r1(Y) (and hence before T1's subsequent w1(Y)). Count these interleavings by fixing the position of T1's third operation r1(Y):
If r1(Y) is at position 5: the first 4 slots must contain a1,a2,b1,b2 in any order preserving each transaction's internal order. That gives C(4,2)=6 ways. The remaining three slots (after r1(Y)) can arrange a4,b3,b4 preserving internal orders in C(3,1)=3 ways. Total = 6×3 = 18.
If r1(Y) is at position 6: the first 5 slots must contain a1,a2,b1,b2 and b3 (b3 can appear only after b2). Ways = C(5,2)=10. The remaining two slots can place a4 and b4 in 2 ways. Total = 10×2 = 20.
If r1(Y) is at position 7: the first 6 slots include a1,a2 and all of b1..b4. Ways = C(6,2)=15. The final slot must be a4. Total = 15×1 = 15.
Summing these gives 18 + 20 + 15 = 53 schedules equivalent to T2→T1, plus 1 equivalent to T1→T2, so the total number of conflict-serializable schedules = 53 + 1 = 54.