Conflict Equivalent

Question

Consider the following ordering S of transaction

T1:R(X),W(Y), T2:R(X),W(Y);T3:R(X),W(Y). how many schedules if any are conflict equivalent to S?

1) 3

2) 5

c) 15

d) 30

Comments

fix w1 -> w2-> w3 . now you need to find number of ways to place r1, r2, r3,

r1 can be place in one way(i.e. before w1) , r2 can be place in 3 ways((here)r1->(here)w1 -> (here)w2), now r3 can be place in 5 ways = ((here)r1->(here) -> w1 ->(here)r2 ->​​​ (here) w2->(here) -> w1 ).

total ways = 1*3*5 = 15

---

Similar questions:

https://gateoverflow.in/118640/gate2017-2-44

https://gateoverflow.in/37446/number-of-conflict-serializible-schedules

https://gateoverflow.in/115201/number-of-schedules-conflict-equivalent-schedule

---

The links are conflict serealizable not conflict equivalient, they both are DIFFERENT!!!

Answer 1

C) 15

---

here we are asked that how many schedules are conflict equivalent to only S: $T_1$ →$T_2$ →$T_3$

total number of concurrent schedules = (2+2+2)! / (2! * 2! * 2!) = 90 ( ref )

but here in these set of transactions it can be seen clearly that on executing them concurrently in any order they are always going to result in a Serializable Schedule. Hence there are 90 serializable schedules.

but we also know that only in 3! ways we can arrange $T_1$, $T_2$ and $T_3$. There are 6(=3!) possible combinations of serial schedules. But we are getting 90 serializable schedules. It means that some schedules are conflict equivalent to each other and simultaneously to a serial schedule out of those 6 serial schedules.

Then 90 is divided into packets of schedules each group(packet) being Conflict Equivalent to one among those 6 serial schedules.

Therefore, 90/6 = 15 schedules exists in a packet. One such packet of schedules is Conflict Equivalent to serial schedule S: $T_1$ →$T_2$ →$T_3$

Answer 2

total schedule = 6!/2!*2!*2! = 90
and every schedule is conflict equal schedule because no cycle in any precedence graph ..
by symmetry each serial schedule must have equal no of conflict schedule..
der are 90 schedule and 3! serial schedule..
T1 ----> T2 ----> T3 is one out of 6 serial schedule.
so no ofconflict equal schedule which is equal to T1 ----> T2 ----> T3
= 90/6 = 15

Comments

I didnt get your Answer by symmetry "Each serial schedule have equal no of Conflict schedule "

I know that a schedule can be serial if it conflict schedule or View Schedule , but i dont have idea  about your statement . Please correct me !

---

but given transaction is always conflict serializable..
der is no cycle in any precedence graph.. every (all 90) precedence graphs are acyclic.

---

Sir, why are we checking for conflict serializable, when the question is asking about the number of conflict equivalent?

Answer 3

option c) 15