Project ForgeConsider a schedule of transactions T1 and T2, in time order: T1:RA, T2:RB, T2:WB, T1:RC, T2:RD, T1:WD, T2:WC, T1:WB, T1:Commit, T2:Commit. (RX = Read(X), WX = Write(X).) Which one of the following schedules is conflict equivalent to the above schedule?
(A) T2:RB, T2:WB, T2:RD, T1:RA, T1:RC, T1:WD, T1:WB, T2:WC, T1:Commit, T2:Commit (B) T1:RA, T1:RC, T1:WD, T1:WB, T2:RB, T2:WB, T2:RD, T2:WC, T1:Commit, T2:Commit (C) T1:RA, T1:RC, T1:WD, T2:RB, T2:WB, T2:RD, T1:WB, T2:WC, T1:Commit, T2:Commit (D) T2:RB, T2:WB, T2:RD, T2:WC, T1:RA, T1:RC, T1:WD, T1:WB, T1:Commit, T2:Commit
- T2:RB, T2:WB, T2:RD, T1:RA, T1:RC, T1:WD, T1:WB, T2:WC, T1:Commit, T2:Commit
- BT1:RA, T1:RC, T1:WD, T1:WB, T2:RB, T2:WB, T2:RD, T2:WC, T1:Commit, T2:Commit
- CT1:RA, T1:RC, T1:WD, T2:RB, T2:WB, T2:RD, T1:WB, T2:WC, T1:Commit, T2:Commit
- DT2:RB, T2:WB, T2:RD, T2:WC, T1:RA, T1:RC, T1:WD, T1:WB, T1:Commit, T2:Commit
Explanation
The original schedule's conflicting-operation pairs (same data item, ≥1 write, different transactions) impose 3 ordering constraints that must be preserved: (1) both of T2's operations on B (RB, WB) occur before T1's WB; (2) T1's RC occurs before T2's WC; (3) T2's RD occurs before T1's WD. Checking each option: (A) T2's RB,WB (positions 1,2) both before T1's WB (position 7) ✓; T1's RC (5) before T2's WC (8) ✓; T2's RD (3) before T1's WD (6) ✓ — all three hold, so A is conflict equivalent. (B) T1's WB happens (position 4) BEFORE T2's RB/WB (5,6) — violates constraint 1. (C) T1's WD (position 3) happens BEFORE T2's RD (position 6) — violates constraint 3. (D) T2's WC (position 4) happens BEFORE T1's RC (position 6) — violates constraint 2. Only option A satisfies all three constraints.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.