GATE CS 2022 Q29 — Transactions and Concurrency Control

To find the serial schedule that is conflict equivalent to the given schedule $S$, we construct its precedence graph. In a precedence graph, a directed edge $T_i \rightarrow T_j$ exists if there is a conflict between an operation in $T_i$ and a subsequent operation in $T_j$.

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. Identify Conflicting Operations

For data item $x$:

• $R_4(x)$ occurs before $W_2(x) \implies T_4 \rightarrow T_2$
• $R_3(x)$ occurs before $W_2(x) \implies T_3 \rightarrow T_2$

For data item $y$:

• $R_1(y)$ occurs before $W_3(y) \implies T_1 \rightarrow T_3$
• $W_1(y)$ occurs before $W_3(y) \implies T_1 \rightarrow T_3$
• $W_1(y)$ occurs before $R_4(y) \implies T_1 \rightarrow T_4$
• $W_3(y)$ occurs before $R_4(y) \implies T_3 \rightarrow T_4$

2. Construct the Precedence Graph

Combining all the directed edges, we get:

• $T_1 \rightarrow T_3$
• $T_1 \rightarrow T_4$
• $T_3 \rightarrow T_4$
• $T_3 \rightarrow T_2$
• $T_4 \rightarrow T_2$

3. Topological Sort

We find the topological order of the vertices in this Directed Acyclic Graph (DAG):

1. $T_1$ has an in-degree of $0$. We select $T_1$ first.
2. After removing $T_1$, the in-degree of $T_3$ becomes $0$. We select $T_3$ next.
3. After removing $T_3$, the in-degree of $T_4$ becomes $0$. We select $T_4$ next.
4. Finally, only $T_2$ remains, which has an in-degree of $0$ now. We select $T_2$.

Thus, the unique topological sort is:

This corresponds to the serial schedule $T_1 \rightarrow T_3 \rightarrow T_4 \rightarrow T_2$.