Conflict Serializabilty

Question

How many conflict equivalent schedules are possible for the given schedule ?

$R_1(A), R_2(A), R_3(A), R_4(A), W_1(B), W_2(B), W_3(B), W_4(B)$

Comments

Post the answer it will be useful for others.

---

is the answer 103 for this plz reply

---

i am getting 24

---

I am also getting 24 @Gurdeep Saini 

---

Rishi yadav

How 24 please explain ??

---

I think i am wrong kumar.dilip

---

i am getting 1560, here's how i tried to solve it, the sequence of reads doesn't matter, whereas writes does matter, so number of possible ways to arrange 4 reads 24, and number of ways to permute 4 writes among 5 places between reads(counting the ends) in order is 65. so total was 65*24.(total number of schedules is 2520 so it is within bounds too).please verify!

Answer 1

I am getting 105 

here's what I did :

fixed r(a) of T1, now r2(A) has three places - before r1(A), after r1(A) and after w1(B) because of two items r1(a) and w1(b) 

now for r3(a), we have 5 places because of 4 items r1(a), r2(a) and w1(b) and w2(b) 

similarly, for r4(a) we have 7 places because of 6 items 

now total possible places would be - 3*5*7 = 105

 

Method 2 :-

Fo with Topological sort method,

Some more references to solve like this problems :-

https://gateoverflow.in/253496/number-of-topological-order

https://gateoverflow.in/245897/hashing-with-linear-probing

Comments

So you are saying that reads can be shuffled but not writes in order to maintain data consistency.

---

In question it is asked - " how many conflict equivalent schedules are possible " , so in whatever schedules we form , for them to be be conflict equivalent  to given schedule , the conflicts need to be resolved in same fashion. So T2>T1 >T3 >T4 would not be be conflict equivalent .

---

@Anuj Mishra

Can we start with $R_{3}$ after fixing $R_{1}$  and then $R_{2 }$ & then $R_{4}$ ??