edited by
13,003 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

Best answer
8 votes
8 votes

We have schedule S with transactions $T_1,T_2.....T_n$

Question says

If S is serializable

Now S can be either Conflict serializable or Can be view Serializable but Not conflict serializable.

Take an example of below schedule

T1      T2
W(A)    
        W(A)
        
W(A)

The precedence graph of above will be cyclic and the above schedule is not Conflict serializable , but View serializable as T2->T1 and hence SERIALIZABLE.

So, clearly my topological sort algorithm would fail on such a precedence graph.

DFS algorithm would only tell about the nature of precedence graph( Like whether it has cycle or not, ancestor-descendants relationship) and this has nothing to do with serializability.Similarly for BFS.

Option (D) is clearly non-sense

Now if I am able to produce a Topological order of a precedence graph, that means the graph is Acyclic and hence the schedule S will be conflict equal to the serial schedule order given by topological order.A conflict equivalent schedule is also view equivalent and hence serializable.

Answer (A).

 

selected by
24 votes
24 votes
Topological Order.
7 votes
7 votes
A.Topological sort

In which we first we perform DFS, then we arrange the vertices in decreasing order of finishing time.
This leads to precedence graph and serial schedule only if graph does not contain cycle.
edited by
3 votes
3 votes

Read properly before you go full bezerk with downvote button.

A serial schedule may or may not be conflict/view equivalent. There are three different things. Serial schedule, Conflict equvalent and view equivalent).

It would be option D and here is why :

S is serializable and we have precedence graph of S. Now serializable has its definition here : http://codex.cs.yale.edu/avi/db-book/db4/slide-dir/ch15-2.pdf

A (possibly concurrent) schedule is serializable if it is equivalent to a serial schedule.  Different forms of schedule
equivalence give rise to the notions of :
1. Conflict serializability
2. View serializability

If a schedule is serializable it may be just view serializable which we will not get from Topological sort. What topological sort actually gives is : Conflict equivalent schedule to some serial schedule. But our question says just Serializable but nothing about conflict or view equivalence, hence topological sort won't gurrantee a serial schedule in case it has cycles.

Carefully study the figure that follows :

Option D will definitly give serial schedule (although it may not be conflict or view equivalent, but it will be serial).

Infact this technique is used in Time Stamp Ordering in which we order transactions in ascending order of their times. It may not give conflict serializbility but it surely gives serial schedule and later we abort and reorder the rule breaking transaction with a new time order.

Kindly comment why it's wrong before down voting.

edited by
Answer:

Related questions

64 votes
64 votes
6 answers
1
Akash Kanase asked Feb 12, 2016
21,840 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,015 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...