edited by
11,165 views
46 votes
46 votes

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?

  1. The schedule is serializable as $T2; T3; T1$

  2. The schedule is serializable as $T2; T1; T3$

  3. The schedule is serializable as $T3; T2; T1$

  4. The schedule is not serializable

edited by

6 Answers

Best answer
49 votes
49 votes

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$

edited by
15 votes
15 votes

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. 

1 flag:
✌ Edit necessary (Harsh Saini_1 “View Serializability is not a Necessary condition for a schedule to be Serializable. An edit is needed”)
8 votes
8 votes
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
2 votes
2 votes

 

Transaction in block and its graph which creates cycle.

Answer:

Related questions

42 votes
42 votes
3 answers
2
Kathleen asked Sep 17, 2014
14,792 views
Consider the following functional dependencies in a database.$$\begin{array}{|l|l|}\hline \text{Date_of_Birth } \to \text{Age} & \text{Age } \to \text{Eligibility} \\\hli...
30 votes
30 votes
7 answers
3
Kathleen asked Sep 17, 2014
9,905 views
Consider the following $2-3-4$ tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in...
42 votes
42 votes
4 answers
4
Kathleen asked Sep 16, 2014
8,876 views
Consider the following SQL querySelect distinct $a_1, a_2, …, a_n$from $r_1, r_2, …, r_m$where PFor an arbitrary predicate P, this query is equivalent to which of the...