UGC-NET NOVEMBER 2017 QUESTIONS WITH EXPLANATION
NTA-NET NOVEMBER 2017 QUESTIONS WITH EXPLANATION
GATE 2016 SET-2 Q:32
Topic: DBMS
Q: 8 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
Answer: (A)
Explanation: For a schedule, we can check its serializability by drawing a precedence graph and find its topological order, precedence graph of schedule must not contain any cycle to be conflict free.
Cycle in precedence graph tells that schedule is not conflict serializable. DFS and BFS traversal of graph are possible even if graph contains cycle. And hence DFS and BFS are also possible for non serializable graphs. But Topological sort of any cyclic graph is not possible. Thus topological sort guarantees graph to be serializable . Option D is not valid because in a transaction with more indices might have to come before lower one. Also two non- conflicting schedule can occur simultaneously.
So, option (A) is correct.
No comments:
Post a Comment