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: Analyze schedule \(S_1\).
Conflicting operations occur on both data items \(x\) and \(y\).
- On \(x\): \(r_2(x)\) occurs before \(w_1(x)\), giving an edge \(T_2 \rightarrow T_1\).
- On \(y\): \(r_1(y)\) occurs before \(w_2(y)\), giving an edge \(T_1 \rightarrow T_2\).

Step 2: Check for cycles in precedence graph of \(S_1\).
The graph contains a cycle \(T_1 \rightarrow T_2 \rightarrow T_1\). Hence, \(S_1\) is not conflict serializable.

Step 3: Analyze schedule \(S_2\).
- On \(x\): \(r_1(x)\) occurs before \(w_1(x)\), and \(r_2(x)\) does not conflict in reverse order.
- On \(y\): \(r_2(y)\) and \(w_2(y)\) occur before \(r_1(y)\), giving a single edge \(T_2 \rightarrow T_1\).

Step 4: Check for cycles in precedence graph of \(S_2\).
The precedence graph has no cycle and corresponds to serial order \(T_2 \rightarrow T_1\).

Step 5: Conclusion.
Thus, \(S_1\) is not conflict serializable, while \(S_2\) is conflict serializable.

Final Answer: (B)