Consider the following four schedules due to three transactions (indicated by…
2014
Consider the following four schedules due to three transactions (indicated by the subscript) using \(read \) and \(write \) on a data item \(x\), denoted by \(r(x)\) and \(w(x)\) respectively. Which one of them is conflict serializable?
- A.
\(r_1(x); r_2(x); w_1(x); r_3(x); w_2(x)\) - B.
\(r_2(x);r_1(x);w_2(x);r_3(x);w_1(x)\) - C.
\(r_3(x);r_2(x);r_1(x);w_2(x);w_1(x)\) - D.
\(r_2(x);w_2(x);r_3(x);r_1(x);w_1(x)\)
Attempted by 113 students.
Show answer & explanation
Correct answer: D
Key idea: build the precedence (conflict) graph and check for cycles.
Apply this to the schedule r2(x); w2(x); r3(x); r1(x); w1(x):
Conflicts and resulting edges:
w2(x) occurs before r3(x) → edge T2 → T3.
w2(x) occurs before r1(x) and before w1(x) → edge T2 → T1.
r3(x) occurs before w1(x) → edge T3 → T1.
There are no cycles in this precedence graph (edges are T2 → T3, T2 → T1, and T3 → T1). Therefore the schedule is conflict serializable and is equivalent to the serial execution: T2 then T3 then T1.
A video solution is available for this question — log in and enroll to watch it.