GATE CS 2016 Set 2 Q22 — Transactions and Concurrency Control

A schedule $S$ is conflict-serializable if and only if its precedence graph (also known as the serialization graph) is acyclic (i.e., a Directed Acyclic Graph or DAG).

In the precedence graph:

• Vertices represent the transactions $T_1, T_2, \dots, T_n$.
• A directed edge $T_i \to T_j$ exists if there is a conflict between an operation in $T_i$ and a subsequent operation in $T_j$, meaning $T_i$ must execute before $T_j$ in any equivalent serial schedule.

For any DAG, a topological sort produces a linear ordering of its vertices such that for every directed edge $u \to v$, vertex $u$ appears before $v$ in the ordering. Therefore, the topological order of the precedence graph is guaranteed to yield a conflict-equivalent serial schedule.

Why the other options are incorrect:

• Depth-first order (B) and Breadth-first order (C): These are graph traversal strategies. The order in which they visit vertices depends on the starting node and the graph structure, and they do not guarantee that for every edge $u \to v$, $u$ is output before $v$.
• Ascending order of transaction indices (D): The transaction indices (like $T_1, T_2, \dots$) are arbitrary labels and do not reflect the actual conflict dependencies of the schedule.