GATE CS 2024 Set 1 — Question 46

To determine which serial schedules are conflict equivalent to $S$, we construct the precedence graph (serialization graph).1. Identify Conflicts:
A conflict exists if two operations belong to different transactions, access the same data item, and at least one of them is a write operation.

• Data item $z$: Accessed only by $T_1$ ($r_1(z), w_1(z)$). No conflicts with other transactions.
• Data item $x$: Accessed only by $T_2$ ($r_2(x), w_2(x)$). No conflicts with other transactions.
• Data item $y$: Accessed by $T_3$ ($r_3(y), w_3(y)$) and $T_2$ ($r_2(y), w_2(y)$).
• $w_3(y)$ occurs before $r_2(y)$: Conflict $T_3 \to T_2$ (Write-Read).
• $w_3(y)$ occurs before $w_2(y)$: Conflict $T_3 \to T_2$ (Write-Write).
• $r_3(y)$ occurs before $w_2(y)$: Conflict $T_3 \to T_2$ (Read-Write).

2. Construct Precedence Graph:

• Nodes: $T_1, T_2, T_3$
• Edges: $T_3 \to T_2$
• $T_1$ has no incoming or outgoing edges (it is isolated).

3. Determine Valid Serial Schedules:
A serial schedule is conflict equivalent to $S$ if it is a topological sort of the precedence graph.

• The constraint is $T_3$ must precede $T_2$.
• $T_1$ can be placed anywhere relative to $T_2$ and $T_3$.

Possible topological sorts:4. Check Options:

• (A) $T_1 T_2 T_3$: Here $T_2$ precedes $T_3$, which violates $T_3 \to T_2$. Incorrect.
• (B) $T_1 T_3 T_2$: $T_3$ precedes $T_2$. Correct.
• (C) $T_3 T_2 T_1$: $T_3$ precedes $T_2$. Correct.
• (D) $T_3 T_1 T_2$: $T_3$ precedes $T_2$. Correct.

Thus, options (B), (C), and (D) are correct.