Consider following schedules involving two transactions: \(S_{1}: \:…
2017
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 of the following statement is true?
- 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 160 students.
Show answer & explanation
Correct answer: C
Build the precedence (conflict) graph between the two transactions T1 and T2. An edge Ti → Tj exists when an operation of Ti precedes and conflicts with an operation of Tj on the same data item.
Schedule S1:
Operations in order: r1(X), r1(Y), r2(X), r2(Y), w2(Y), w1(X).
r1(Y) occurs before w2(Y) → conflict (read-write) gives edge T1 → T2.
r2(X) occurs before w1(X) → conflict (read-write) gives edge T2 → T1.
Since the graph has edges T1 → T2 and T2 → T1, there is a cycle. Therefore S1 is not conflict serializable.
Schedule S2:
Operations in order: r1(X), r2(X), r2(Y), w2(Y), r1(Y), w1(X).
r2(X) occurs before w1(X) → conflict (read-write) gives edge T2 → T1.
w2(Y) occurs before r1(Y) → conflict (write-read) gives edge T2 → T1.
All conflict edges point from the second transaction to the first (T2 → T1) and there is no edge T1 → T2, so there is no cycle. Therefore S2 is conflict serializable (equivalent to the serial order: second transaction before first).
Final conclusion: S1 is not conflict serializable, and S2 is conflict serializable.
A video solution is available for this question — log in and enroll to watch it.