Suppose a database schedule S involves transactions \(T_1, ..., T_n\).…
2016
Suppose a database schedule S involves transactions \(T_1, ..., T_n\). Construct the precedence graph of \(S\) with vertices representing the transactions and edges representing the conflicts. If \(S\) is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to yield a serial schedule?
- A.
Topological order
- B.
Depth-first order
- C.
Breadth-first order
- D.
Ascending order of transaction indices
Attempted by 331 students.
Show answer & explanation
Correct answer: A
Key insight: if the schedule S is serializable then its precedence graph is acyclic, and any topological ordering of that graph yields a serial schedule that is conflict-equivalent to S.
Build the precedence graph: vertices = transactions, directed edges = conflict dependencies (u → v means u must come before v).
If the graph has no cycles (i.e., S is serializable), compute a topological ordering so every edge goes from an earlier vertex to a later vertex.
Execute transactions in that topological order. Because all precedence edges are respected, the resulting schedule is serial and conflict-equivalent to the original schedule.