319 views
$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 | 319 views
Conflict Equivalent = View Equivalent = 15

Am I right?
explain how you got that ??

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$T

yes 15 conflict serializable schedules  but what about view serial schedules ??
As we know every conflict serializable schedule is view serializable,

total view equivalent schedule = 15
there can be view serializable which are not conflict serialiable ??
you're right there can be few CSS which are not V.SS
How to find them ?
there is only manual approach, there are 15 CSS as above explained but how many are VSS
i think there are 4 VSS
View Serializable  =  C.S + V.S but not C.S

So V.S schedules will be greater than C.S.

It is true that VSS will be more than CSS. For that, there must be a blind write operation in schedule.

Coming to this particular problem,

Total number of concurrent schedules =  6! / (2! * 2! * 2!) = 90

Total number of serial schedules = 3! = 6

So total number of concurrent schedules corresponding to particular serial schedule = 90/6 = 15

$\therefore$ for , T1 $\rightarrow$T2 $\rightarrow$T, this serial schedule number of concurrent schedules = 15 and all these 15 schedules are CSS(as proved above) and therefore VSS also. We can't get more than 15 schedules for T1 $\rightarrow$T2 $\rightarrow$T3 . So, this should be answer.

But given ans is 15 CS and  30 VS
Any explanation given?
Nope :(
@kantikumar Here also we have blind writes ...

Yes, we do have blind writes here, but we also calculated total number of concurrent schedules for T1 $\rightarrow$T2 $\rightarrow$T3, which is 15. $\therefore$Answer cant be more than 15 for T1 $\rightarrow$T2 $\rightarrow$T3

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

Every conflict serializable schedule is also view serializable ,  but every view serializale schedule is not conflict serializable .

That means conflict serializable is subset of view serializable. More number of vew serial schedule is possible.

Also in this question , number of view-equivalent schedules of given schedule is asked .

There is a difference between view equal and view equal to a serial schedule.

View equal schedule = (concurrent + serial )  schedule

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

If a schedule S is view-equivalent to a serial schedule, we say S is view-serializable , Clearly view equal and view serializable are different from this line .

If it is given view equal only then it can include concurrent schedules also .That is the reason we can't draw polygraph here..as in polygraph we draw it for serial schedules only .

We assume either one transaction executes before or after another in serial schedule but the operations of two can be interleaved in between in concurrent schedule.

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 is fixed.

so number of view equal schedule is 30 .

+1 vote

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
@prabhanjan
I think answer is 15 only for both, every CSS is VSS

+1 vote
1
+1 vote
2