Let \(r_i(z)\) and \(w_i(z)\) denote read and write operations respectively on…
2021
Let \(r_i(z)\) and \(w_i(z)\) denote read and write operations respectively on a data item \(z\) by a transaction \( T_i \) . Consider the following two schedules.
\(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 options is correct?
- A.
\(S_1\)is conflict serializable, and\(S_2\)is not conflict serializable. - B.
\(S_1\)is not conflict serializable, and\(S_2\)is conflict serializable - C.
Both
\(S_1\)and\(S_2\)are conflict serializable - D.
Neither
\(S_1\)nor\(S_2\)is conflict serializable
Attempted by 212 students.
Show answer & explanation
Correct answer: B
Key idea: build the precedence (conflict) graph between transactions by looking at conflicting reads/writes on the same data items.
For S1 = r1(x) r1(y) r2(x) r2(y) w2(y) w1(x):
Conflicts produce edges:
r1(y) before w2(y) gives T1 -> T2.
r2(x) before w1(x) gives T2 -> T1.
These two edges form a cycle (T1 <-> T2), so S1 is not conflict-serializable.
For S2 = r1(x) r2(x) r2(y) w2(y) r1(y) w1(x):
Conflicts produce edges:
r2(x) before w1(x) gives T2 -> T1.
w2(y) before r1(y) gives T2 -> T1.
All edges go from T2 to T1 and there is no edge from T1 to T2, so the precedence graph is acyclic and S2 is conflict-serializable (equivalent to serial order T2 then T1).
Final answer: S1 is not conflict-serializable; S2 is conflict-serializable.
A video solution is available for this question — log in and enroll to watch it.