Question

Suppose a database schedule 5 involves transactions T₁, T₂, .............T_n 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 ?
1. Topological order
2. Depth - first order
3. Breadth - first order
4. Ascending order of transaction indices

Answer 1

Correct Answer - Option 1 : Topological order

The correct answer is option 1

• For a schedule to be conflict serializable, there should be no cycle present in the precedence graph.
• Topological sort is not possible for the cyclic graph.
• Hence topological ordering of the vertices is guaranteed to yield a serial schedule.

• BFS and DFS are also possible for cyclic graphs.
• Ascending order of transactions indices also does not guarantee serial a serial schedule because in a transaction more indices might come before the lower one.