1,242 views
1 votes
1 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 respec

tively. GATECS2003Q87

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

2 Answers

3 votes
3 votes
it is not serializable...

start checking with onflict serializable or not...if not then go for view serilisability if any blind write is there..

there is a loop in graph between T1 and T2 because of R(D1) and W(D1) and R(D2) and W(D2)...so it is no conflict serialisable

now check for any blind writes(writing without reading anything)...there are no blind writes present so it is not view serialisable also

hence option D..
2 votes
2 votes

For serialisability we first check using precedence graph as mentioned earlier.In the precedence the vertices represent transaction and the edges in the precedence graph will be the conflict pairs.We have edge between Ti and T transaction iff :

I) Ti  before Tj

II) Either read/write , write/read or write write pair exists between these 2 transactions on the same variable.e.g.  R1(X) and W2(Y) will not be a conflict pair since read write pair is not on same variable.

So following these rules we construct the precedence graph .If there is a cycle we conclude that it is not conflict serialisable as the case here we have cycle between T1 and T2 due to W(D1) - R(D1) pair we will have edge from T1  to T2 and  T2  to T1 edge due to W(D2) and R(D2).

So it is not conflict serialisable so we have to check for view serialisability.If it were conflict serialisable , then no need to check further as every conflict serialisable schedule is  view serialisable.

The default meaning of serialisability is referred to view serialisability as it is more general than conflict serialisability.So we have to check further.

We have to remember 2 things :

a) If a schedule is  conflict serialisable , then it is  also view serialisable and hence by default serialisable.

b) If a schedule is not conflict serialisable , however , then it may or may not be view serialisable and hence may or  may not be serialisable.So we have to check the conditions of view serialisablilty in that case which are :

i) Initial read for view equal serial schedule of each variable should be same

ii) Updated read pair of each variable between pair of transactions should be same in both given non serial schedule in the question as well as view equal serial schedule if it exists.

iii) Final write of each variable should also be same in both non serial and corresponding view equal serial schedule.

If these conditions are met then only we say a non serial schedule is serialisable schedule.So one has to be careful about the default meaning of serialisability which is view serialisability.

Now lets use the i) , ii) and iii) conditions mentioned above.Here we have to use partly elimination approach and partly the rules which I mentioned for checking view serialisability.

To satisfy initial read condition u have to ensure that T2 comes first in the view equal serial schedule as D3 and D2 variables are read by T2 first in the given schedule without having any write on them.

So T2 comes compulsorily in 1st place.So option C is eleiminated.

Now to decide whether T1 or T3 comes next in the serial schedule that there is an initial read of D1 variable which is being performed is by T1 so T1 must come before T3.This way option A is also discarded.Thus the only possible view equal serial schedule which we can have is : 

T2 : T1 : T3

Now we have to check the validity of this serial schedule using updated read and final write condition.But here checking the final write condition on variable D1 is sufficient.Let us see how.

In the given non serial schedule the final write on D1 is done by T2 whereas according to the serial schedule T2 : T1 : T3 , D1 is written finally by transaction T1 which is not according to the given schedule.

Hence we can say it is not view equal to serial schedule to the schedule T2 : T1 : T3.

Hence B) option is also eliminated.

Hence we can conclude it is non serialisable.

Hence D) option is correct.

Related questions

0 votes
0 votes
2 answers
1
joshipratik232 asked Aug 16, 2022
453 views
Does Conservative 2PL ensures Recoverability ? If Yes then Does it ensures Cascadeless or Strict recoverable schedule ?
0 votes
0 votes
0 answers
2
gatecrack asked Sep 5, 2018
378 views
Consider th following scheduler1(A)r2(B)r3(C)w1(B)w2(C)w3(D)Find the schedule which are possible to execute by strict 2PL protocol? consider commit operation as immediate...
1 votes
1 votes
1 answer
3