Discussion
Suppose a database schedule S involves transactions T1, ..., Tn. 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?
Answer: A
A serial schedule is guaranteed by a topological order of the precedence graph.
An edge \(T_{i} \to T_{j}\) means an operation of \(T_{i}\) conflicts with and precedes one of \(T_{j}\), so any equivalent serial schedule must run \(T_{i}\) before \(T_{j}\). A conflict-serializable schedule has an acyclic precedence graph, and a topological order lists every vertex after all its predecessors, respecting every edge.
Depth-first and breadth-first orders need not respect edge directions (a vertex can be visited before one of its predecessors), and transaction indices have nothing to do with the conflict order.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development