GATE CS 2007 Q64 — Transactions and Concurrency Control

To determine if the schedules are conflict serializable, we construct the precedence graph for each schedule. A schedule is conflict serializable if and only if its precedence graph contains no cycles.

Recall that two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation.

1. Analysis of Schedule $S_1$

$$S_1 : r_1(X); r_1(Y); r_2(X); r_2(Y); w_2(Y); w_1(X)$$

Let's identify the conflicting operations between different transactions:

• Conflict on $Y$: $r_1(Y)$ occurs before $w_2(Y)$. This creates a dependency edge:
  $$T_1 \to T_2$$
• Conflict on $X$: $r_2(X)$ occurs before $w_1(X)$. This creates a dependency edge:
  $$T_2 \to T_1$$

Since there is a cycle ($T_1 \to T_2 \to T_1$) in the precedence graph, $S_1$ is not conflict serializable.

2. Analysis of Schedule $S_2$

$$S_2 : r_1(X); r_2(X); r_2(Y); w_2(Y); r_1(Y); w_1(X)$$

Let's identify the conflicting operations between different transactions:

• Conflict on $Y$: $w_2(Y)$ occurs before $r_1(Y)$. This creates a dependency edge:
  $$T_2 \to T_1$$
• Conflict on $X$: $r_2(X)$ occurs before $w_1(X)$. This creates a dependency edge:
  $$T_2 \to T_1$$

The only directed edge in the precedence graph is $T_2 \to T_1$. Since there are no cycles, $S_2$ is conflict serializable (with the equivalent serial order $T_2 \to T_1$).

Thus, $S_1$ is not conflict serializable and $S_2$ is conflict serializable.