GATE CSE 2016 Set 2 | Question: 22

Question

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?

• A. Topological order
• B. Depth-first order
• C. Breadth-first order
• D. Ascending order of the transaction indices

Comments

Precedence graph of a serializable schedule contains no cycles. Moreover, the edges are directed. Hence, precedence graph of a serializable schedule is a DAG.

 

Options B, C and D would work even for a cyclic or undirected graph; and we don't want that.

---

Serial schedule possible only if graph does not contain cycle . And a graph with a topological sort must be an acyclic graph.

BFS and DFS can work both cyclic and acyclic graphs.

---

The confusion in this question is being created due to the fact a schedule can be serializable without being conflict serializable. 

But we all are missing an important line in question

which one of the following orderings of the vertices of the precedence graph

Precedence graph is already created and we have to order it's vertices so only topological sorting can give us conflict equivalent serial schedule. So we can safely assume in this question  $serializable$ $\equiv$ $conflict \hspace{0.2cm} serializable $

Option D could have been the answer because any order of serial execution is serializable but ordering vertices in ascending order of transaction indices will give us serializable schedule but not conflict serializable.

Answer 1

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).

 

Comments

@  Ayush Upadhyaya could you please explain how is this view serializable?

---

@Ajit J-Here there are no initial reads of the item A. Also, there are no updated reads.The final write of data item A is performed by T1.So, T1 must come after T2.Hence Serializable as T2->T1 and if you execute also, take some example of value of A, and try executing in order and you'll find the result is still same if transactions are executed in order t2>t1

---

@Ayush Upadhyaya Thanks brother

---

@Ayush Upadhyaya

Why D) doesnot makes sense?

Chk this question https://gateoverflow.in/39703/gate2016-1-51

exclusive locks to O1,…,Ok in increasing order of their addresses.

ensures serializability. Same thing can happen here too, isnot it?

---

@srestha
Increasing order of indices ensures deadlock freedom there, not serializablity (for serializablity they have used 2PL algo.)

---

In that question if its ask "the best algoritham to find our schedule is serializable or not " so which one more better in dfs and bfs ??? @Anyone

---

and  topological sort is not used in that case

Answer 2

Topological Order.

Comments

@ srestha Does backtracking results in cycles?

---

@Bikram please look into this.

Given S is a Serializable schedule.

Let’s take the case of S being View Serializable but not Conflict Serializable. Then precendence graph of S contains cycle and topological sort is not possible.

---

mani312

yes!

but for a view serializable schedule we can make a polygraph and we can get the serial order from it.

Answer 3

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.

Comments

What is wrong with option D.

Answer 4

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.

Comments

st360 same here !! thanks for participating in dicussion :)

---

Last point..
Question says..which of the following is guarenteed to yield a serial schedule..
in case of cycles.. the topological sort wont yield a schedule, because algorithm wont work.. but in other cases when it does yield a schedule.. it clearly gives the serial order, other options donot guarentee to give the serial order..

---

Counter example to Option D.

 

We should follow the arrows. So, it'll be T1 —> T3 —> T2.

Since there's a conflict from T3 to T2, if we execute T2 before T3, consistency could be violated.