Consider following schedules involving two transactions: \(S_{1}: \:…
2018
Consider following schedules involving two transactions:
\(S_{1}: \: r_{1}(X);r_{1}(Y);r_{2}(X);r_{2}(Y);w_{2}(Y);w_{1}(X) \\ S_{2}: \: r_{1}(X);r_{2}(X);r_{2}(Y);w_{2}(Y);r_{1}(Y);w_{1}(X)\)
Which one of the following statements is correct with respect to above ?
- A.
Both 𝑆1 and 𝑆2 are conflict serializable.
- B.
𝑆1 is conflict serializable and 𝑆2 is not conflict serializable
- C.
𝑆1 is not conflict serializable and 𝑆2 is conflict serializable
- D.
Both 𝑆1 and 𝑆2 are not conflict serializable
Attempted by 191 students.
Show answer & explanation
Correct answer: C
Final answer: S1 is not conflict serializable; S2 is conflict serializable.
Analysis of schedule S1:
Conflicting pair: r1(Y) occurs before w2(Y), so there is an edge from transaction 1 to transaction 2.
Conflicting pair: r2(X) occurs before w1(X), so there is an edge from transaction 2 to transaction 1.
These edges create a cycle (transaction 1 -> transaction 2 -> transaction 1), so the precedence graph is cyclic and S1 is not conflict serializable.
Analysis of schedule S2:
Conflicting pair: r2(X) occurs before w1(X), which gives an edge from transaction 2 to transaction 1.
Conflicting pair: w2(Y) occurs before r1(Y), which also gives an edge from transaction 2 to transaction 1.
All conflict edges point from transaction 2 to transaction 1; there is no cycle, so the precedence graph is acyclic and S2 is conflict serializable.
Equivalent serial order: transaction 2 then transaction 1.
Tip: To determine conflict serializability, list all pairs of conflicting operations on the same data item performed by different transactions, draw edges in a precedence graph from the earlier transaction to the later one, and check the graph for cycles. A cycle means not conflict serializable; no cycle means conflict serializable.