Question 32

The precedence graph (or serialization graph) for a schedule $S$ is a directed graph $G = (V, E)$ where:

• The vertices $V$ represent the committed transactions $\{T_1, \dots, T_n\}$.
• A directed edge $T_i \to T_j$ exists if there is a conflict operation in $T_i$ that precedes a conflicting operation in $T_j$.

By the Conflict Serializability Theorem, schedule $S$ is conflict serializable if and only if its precedence graph $G$ is acyclic (a DAG).

A topological sort of a DAG produces a linear ordering of its vertices such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering.

Executing the transactions sequentially in topological order preserves the order of all conflicting operations in $S$, thereby yielding an equivalent serial schedule.

Therefore, a Topological order is guaranteed to yield a valid serial schedule (option A).