retagged by
4,914 views
6 votes
6 votes
$1)$ Find the number of all possible conflict-equivalent and view-equivalent schedules to the following serial schedules.

    (a) r1(A), w1(B), r2(A), w2(B), r3(A), w3(B).
retagged by

3 Answers

Best answer
7 votes
7 votes

It is simple permutation.

Given :Transactions T1 T2 T3 each having 2 operations R(A) W(B).

Serial schedule : T1 $\rightarrow$T2 $\rightarrow$T

Total number of operations= 6

Total permutations possible = 6!

But, those 2 operations of each Tx should appear in particular order. $\therefore$ divide with 2! for each Tx

Also W1(B) W2(B) W3(B) should appear in this order. $\therefore$ divide with 3!

i.e 6! / (2! * 2! * 2! * 3!) = $15$

This is total number of conflict-equivalent schedules possible for T1 $\rightarrow$T2 $\rightarrow$T3  


Total view equivalent schedules = $30$

Hence total number of conflict equivalent schedule is 15 and total number of view equivalent schedule is 30 .

edited by
4 votes
4 votes

Here blind write perform by w1(B) and w2(B) , blind write means write before read. 

now, w3(B) is fixed due to the rule "last operation on some item should be same in view equivalence schedule."

so leaving w3(B) we have 5 schedule, we can arrange them in 5! = 120 way .

r3(A) can be arranging 2! way 

r2(A) can be arranging 2! way

so total number of view equal schedule possible (120 / 2! 2! ) = 30

in all these 30 schedules  w3(B) is last transaction , it's fixed.

so number of view equal schedule is 30 .

And remember view equal is different from view equal to a serial schedule.

View equal schedule = (concurrent + serial )  schedule

View view-equivalent schedules to a serial schedule = only serial schedule to consider 

the difference is the word " serial " !!

In this question only view equal is asked . 

hope this is clear now ...

edited by
0 votes
0 votes
final write in T3 it cannot change either it starts from t1 or t2

T1-.>T2->T3

T2->T1->T3
Answer:

Related questions

1 votes
1 votes
2 answers
2