GATE 2017 CS (CS2) – Question 54
Transactions are T₁:r₁(X)w₁(X)r₁(Y)w₁(Y) and T₂:r₂(Y)w₂(Y)r₂(Z)w₂(Z). How many interleavings preserve each transaction’s order and are conflict-serializable?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 54.0 to 54.0
Explanation
Only Y operations conflict. For T₁→T₂, w₁(Y) must precede r₂(Y), allowing only the fully serial T₁-then-T₂ schedule: one. For T₂→T₁, w₂(Y) must precede r₁(Y). If r₁(Y) occupies position j=5,6,7, choose two earlier T₁ operations and the one later T₁ operation: $\sum_{j=5}^7\binom{j-1}{2}(8-j)=18+20+15=53$. Other interleavings have a cycle. Total 1+53=54.