edited by
12,995 views
34 votes
34 votes

Suppose a database schedule $S$ involves transactions $T_1,\ldots,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?

  1. Topological order
  2. Depth-first order
  3. Breadth-first order
  4. Ascending order of the transaction indices
edited by

6 Answers

3 votes
3 votes

Answer - Topological Order!

Serial schedule will have no cycles ever present in it's equivalent graph!

Now, Topological Sorting Algorithm also works only on Directed Acyclic Graph (DAG). Therefore you do this - 

1) Make sure the graph has no cycles and that's fine as they mentioned in question, guaranteed a serial schedule and yes, serial schedule will have no cycles, also they mentioned conflicts are mentioned on edges therefore you get the directions making the precedence graph as DAG

2) On this Directed Acyclic Graph, you call DFS Algorithm.

3) Now DFS always visits each vertex in the graph and in the output it produce the sequence in which DFS visited the vertices of your DAG.

4) Now, reverse the output of DFS i.e you reverse the order and you will get your topological sort.

One thing more, Topological sort is not unique! 

1 votes
1 votes
DFS and BFS traversal are possible if the graph contain cycle but topological sort of any cyclic graph is not possible.
Answer:

Related questions

64 votes
64 votes
6 answers
1
Akash Kanase asked Feb 12, 2016
21,837 views
Consider the following database schedule with two transactions $T_{1}$ and $T_{2}$.$S= r_{2}\left(X\right); r_{1}\left(X\right); r_{2} \left(Y\right); w_{1} \left(X\right...
56 votes
56 votes
1 answer
2
Akash Kanase asked Feb 12, 2016
11,007 views
Consider the following database table named water_schemes:$$\overset{\text{Water_schemes}}{\begin{array}{|c|c|c|}\hline\textbf{scheme_no}& \textbf{district_name}& \te...