GATE CS 2021 Set 1 Q32 — Transactions and Concurrency Control

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

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 find the conflicting operations between transactions $T_1$ and $T_2$:

• On item $y$: $r_1(y)$ occurs before $w_2(y)$. Since $r_1(y)$ and $w_2(y)$ conflict, this creates a directed edge: $$T_1 \to T_2$$
• On item $x$: $r_2(x)$ occurs before $w_1(x)$. Since $r_2(x)$ and $w_1(x)$ conflict, this creates a directed edge: $$T_2 \to T_1$$

The precedence graph for $S_1$ contains the cycle $T_1 \to T_2 \to T_1$. Therefore, $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 find the conflicting operations between transactions $T_1$ and $T_2$:

• On item $x$: $r_2(x)$ occurs before $w_1(x)$. This creates a directed edge: $$T_2 \to T_1$$
• On item $y$: $w_2(y)$ occurs before $r_1(y)$. This creates a directed edge: $$T_2 \to T_1$$

The precedence graph for $S_2$ has only one directed edge, $T_2 \to T_1$, and contains no cycles. Therefore, $S_2$ is conflict serializable (equivalent to the serial execution order $T_2 \to T_1$).

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