Question

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. 
\[ \begin{aligned} 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) \end{aligned} \] 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.

Hint:

A schedule is conflict serializable if and only if its precedence graph is acyclic.

Answer 1

The Correct Option is B

Step 1: Examine conflicting operations in schedule S₁.
In S₁, conflicts occur on both data items x and y.

• On x: the read operation r₂(x) occurs before the write operation w₁(x), which introduces an edge T₂ → T₁ in the precedence graph.
• On y: the read operation r₁(y) occurs before the write operation w₂(y), giving an edge T₁ → T₂.

---

Step 2: Check for cycles in the precedence graph of S₁.
The precedence graph contains the cycle:

T₁ → T₂ → T₁

Since a cycle exists, S₁ is not conflict serializable.

---

Step 3: Examine conflicting operations in schedule S₂.
In S₂, the conflicts are analyzed as follows:

• On x: operations r₁(x) and w₁(x) belong to the same transaction and do not create inter-transaction conflicts. The operation r₂(x) does not violate serializability.
• On y: r₂(y) and w₂(y) occur before r₁(y), resulting in a single edge T₂ → T₁.

---

Step 4: Check for cycles in the precedence graph of S₂.
The precedence graph contains only one directional edge and no cycles.

Hence, S₂ is equivalent to the serial order T₂ → T₁.

---

Final Conclusion:
Schedule S₁ is not conflict serializable, while schedule S₂ is conflict serializable.

Final Answer: (B)