Suppose a database schedule S involves transactions T1 , T2 , .............,Tn…
2017
Suppose a database schedule S involves transactions T1 , T2 , .............,Tn . Consider 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 256 students.
Show answer & explanation
Correct answer: A
Main idea: If the schedule is conflict-serializable, its precedence graph has no directed cycles (it is a directed acyclic graph, or DAG).
A topological ordering of the DAG arranges transactions so that for every directed edge from one transaction to another, the source transaction appears earlier in the order.
Executing transactions serially in any topological order preserves the order of all conflicting operations, so the resulting serial schedule is conflict-equivalent to the original schedule.
How to obtain such an order: run any topological sort algorithm (for example, Kahn's algorithm or a DFS-based method using finishing times). If a cycle is detected, the schedule is not conflict-serializable.
Conclusion: A topological ordering of the precedence graph is guaranteed to yield a serial schedule when the schedule is serializable, because it respects all conflict dependencies.
A video solution is available for this question — log in and enroll to watch it.