Madeeasy

Question

S : r1(A), r2(A), r3(A), r4(A), w1(B), w2(B), w3(B), w4(B) The number of serial schedules equal to schedule(S) but not conflict equal to schedule(S)
answer given is 5.

What i understood is for schedule to be serial. r1(A) & w1(B) must be together.

Similarly r2(A) & w2(B) must be together

Similarly r3(A) & w3(B) must be together

Similarly r4(A) & w4(B) must be together

Now w4(B) must be last one to write B.

But we can order T1, T2 &T3 in any order. 3! =6

So I am getting 6 as answer , but not 5

Comments

what about the initial read condition as T1 is reading initial data item from database so it should occur before T2 T3 because they have also their first operation as R(A).

in that case it should have 3 view equiv schedules that are not confl equiv to S

---

we are only swapping three writes w1(B), w2(B), w3(B) in 3! ways out of which one schedule containing w1(B), w2(B), w3(B) in the same order will be conflict serializable.

---

@balchandar reddy san i have just 1 doubt .

if the schedule 'S1' has to be view equivalent with a given schedule 'S' then if a transaction is reading a data item initially from database in schedule 'S' then in schedule 'S1' the same transaction should read the data item from database.

why are you not considering this condition in your answer?

Answer 1

I found why it is 5.

for schedule to be serial. r1(A) & w1(B) must be together.
Similarly r2(A) & w2(B) must be together
Similarly r3(A) & w3(B) must be together
Similarly r4(A) & w4(B) must be together
Now w4(B) must be last one to write B.
But we can order T1, T2 &T3 in any order. 3! =6

So 6 is number of serial schedule (It is not view serial schedule , as for view serial we have to fix r1(A) also )

from this we have to subtract conflict equal schedule. 

To find number of conflict equal schedule draw dependency graph like.

 

T1 must precede T2,T3&T4 hence there is edge from T1 to T2,T3&T4

T2 must precede T3 & T4 hence there is edge from T2 to T3 & T4

T3 must precede T4 . Hence there is edge from T3 to T4.

Now find topological path from T1 to T4 {that must include all four transaction}

There only one such path i.e. T1->T2->T3->T4

hence 6-1 =5

please reply if you find something wrong in answer

Comments

you said 6 is the no of serial schedule that seems wrong

as total no of serial schedules present here are 4! i.e 24