Consider the following three schedules of transactions T1, T2 and T3.…
2008
Consider the following three schedules of transactions T1, T2 and T3. [Notation: In the following NYO represents the action Y (R for read, W for write) performed by transaction N on object O.]
(S1) 2RA 2WA 3RC 2WB 3WA 3WC 1RA 1RB 1WA 1WB
(S2) 3RC 2RA 2WA 2WB 3WA 1RA 1RB 1WA 1WB 3WC
(S3) 2RA 3RC 3WA 2WA 2WB 3WC 1RA 1RB 1WA 1WBWhich of the following statements is TRUE?
- A.
S1, S2 and S3 are all conflict equivalent to each other
- B.
No two of S1, S2 and S3 are conflict equivalent to each other
- C.
S2 is conflict equivalent to S3, but not to S1
- D.
S1 is conflict equivalent to S2, but not to S3
Attempted by 98 students.
Show answer & explanation
Correct answer: D
Answer: S1 is conflict equivalent to S2, but not to S3.
Key observation: Only operations on object A create conflicts between different transactions; operations on B and C do not change the inter-transaction conflict ordering across the schedules.
Order on object A in S1: T2 reads A, T2 writes A, T3 writes A, T1 reads A, T1 writes A — note that T2's write occurs before T3's write.
Order on object A in S2: T2 reads A, T2 writes A, T3 writes A, T1 reads A, T1 writes A — identical ordering to S1 for the conflicting operations (T2's write before T3's write).
Order on object A in S3: T2 reads A, T3 writes A, T2 writes A, T1 reads A, T1 writes A — here the write by T3 on A occurs before the write by T2, reversing the conflict order seen in S1 and S2.
Conclusion: Because S1 and S2 have identical ordering of all conflicting operations they are conflict equivalent. S3 differs in the order of the conflicting writes on object A (T3 before T2), so S3 is not conflict equivalent to S1 and S2.