GATE CSE 2003 | Question: 87

Question

Consider three data items $D1, D2,$ and $D3,$ and the following execution schedule of transactions $T1, T2,$ and $T3.$ In the diagram, $R(D)$ and $W(D)$ denote the actions reading and writing the data item $D$ respectively.
$$ \begin{array}{|l|l|l|}\hline \textbf{T1}  &  \textbf{T2} & \textbf{T3}  \\\hline \text{} & \text{R(D3);} & \text{}\\ \text{} & \text{R(D2);} & \text{} \\ \text{} & \text{W(D2);} & \text{} \\ \text{} & \text{} & \text{R(D2);} \\ \text{} & \text{} & \text{R(D3);} \\ \text{R(D1);} & \text{} & \text{} \\ \text{W(D1);} & \text{} & \text{} \\ \text{} & \text{} & \text{W(D2);} \\ \text{} & \text{} & \text{W(D3);} \\ \text{} & \text{R(D1);} & \text{} \\ \text{R(D2);} & \text{} & \text{}   \\ \text{W(D2);} & \text{} & \text{} \\ \text{} & \text{W(D1);} & \text{}\\\hline \end{array}$$Which of the following statements is correct?

• A. The schedule is serializable as $T2; T3; T1$

• B. The schedule is serializable as $T2; T1; T3$

• C. The schedule is serializable as $T3; T2; T1$

• D. The schedule is not serializable

Comments

@Abhrajyoti00 can u explain the polygraph for this ? and there are some schedules that are not vs and not cs but still serializable so what about them how can we check them ?

---

Serializable check is very easy. Just see if you can serialize the schedule. It means if T1-T2 or T2-T1 any one of the serial schedule can be made such that there's no change in database as the original one, then it is serializable. You can see @Deepak Poonia Sir's explanation on Serializability in Go classes YT channel.

---

@Abhrajyoti00 can u plz send the link here as i am not able to see it on yt channel ?

Answer 1

There is a cycle in precedence graph so schedule is not conflict serialisable.
Check View Serializability:
Checking View Serializability is NPC problem so proving by contradiction..

1. Initial Read
   $T2$ read $D2$ value from initial database and $T1$ modify $D2$ so $T2$ should execute before $T1$.
   i.e., $T2 \to T1$
    
2. Final write.
   final write of $D1$ in given schedule done by $T2$ and $T1$ modify $D1$ i.e. $W(D1)$..
   that means $T2$ should execute after $T1$.
   i.e., $T1 \to T2$

So, schedule not even View Serializable.
Not Serializable.

Correct Answer: $D$

Comments

for checking view serialization, there is a more simple explanation than checking NPC and contradictory proofing,

ie. just check if there is any blind write in the execution schedule of transactions, if yes then only we need to form view equivalence graph.

in this case there is no blind write under either of the three transactions, so we can say that its not view serializable.hence, not serializable.

option d is right one

---

we can also draw the polygraph and check for view serializability

---

Having blind writes does not imply that it is view serializable.A schedule which is not conflict serializable will be having two choices :

    1)Not containing Blind writes : then surely it will not be view serializable and thus not Serializable.

   2)Containing Blind writes : it may/may not be view serializable. Then we will go for the Polygraph.

---

related ques

https://gateoverflow.in/185820/draw-polygraph-of-this-check-for-view-serializability?show=185866

---

1)if schedule(s) not conflict serializable schedule && no blind write in schedule(s),then then schedule also not view serializable schedule.

2)if schedule(s) not conflict-serializable schedule && schedule(s) is view serializable schedule , then atleast one blind write must exist.

---

@AakS I totally agree with yur statement ,

but in this particular example we can easily see no blind writes are there hence we can reach conclusion (as in my case proving with contradiction may takes longer time in real exam).

---

Can anyone provide a good resource to learn how to draw polygraph..

Thanks in advance :)

---

Can we try to swap nonconflicting instructions (like it's done in Korth) and use that to show that serializability is not possible? Or is that applicable only to conflict serializability and not view serializability?

Edit: To answer my own question, this is only for conflict serializability checking. For view serializability follow the blind write check method given in above comments.

Answer 2

Conflict Serializability is  the sufficient condition for a schedule to be Serializable while View Serializability is the Neccassary and Sufficient condition for a Serializable schedule.

So first we will check conflict serializability using precendence graph. Here it containing the cycle and thus it fails for conflict serializability.Now we will go for the Blind Writes check.

if a schedule is not conflict serializable and not containing the blind writes then it FAILS for view serializability also.

As given schedule not containing any Blind write, it is not View serializable.Thus, the given schedule is not Serializable. 

Comments

No, View Serializability is not a necessary condition for serializability. It is sufficient for serializability.

See the diagram below for better understanding. 

 

Answer 3

The above schedule is not conflict serializable as there is a cycle in the precedence graph .Also no blind writ in any of the three transactions (i.e write without read ) which is a must condition for view serializable  . So it is not serializable.

For Serializable : A schedule is serializble if it is either conflict serializable or view serializable  So simple and easy

Answer 4

 

Transaction in block and its graph which creates cycle.