Question

Number of conflict serializable schedules in

T1 : R(A) W(A) R(B) W(B)

T2: R(A) W(A) R(B) W(B)

Comments

@Himanshu1

Have you find schedules equivalent to T2->T1 only

M getting 12 schedules equivalent to T1->T2 itself !!!

---

Can someone solve it using topological sort ?

---

Similar questions:

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

https://gateoverflow.in/10299/conflict-equivalent

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

Answer 1

answer is 12

 

similary to for

case t2->t1 you will get 6 more

NOTE:

in 12 schedule 2 serial schdeule is also included

Comments

What is that diagram showing? Can u plz tell that box diagram is telling what?

---

https://gateoverflow.in/247402/self-doubt-conflict-serializable

How to solve the above ques with this method?

Answer 2

Schedules conflict equivalent to serial schedule $T1 \rightarrow T2 :$

$R2(A) $ must occur after $W1(A),$ and $R2(B)$ must occur after $W1(B)$ and within a transaction, order of operations must remain same, hence,  The only possibility is $R1(A), W1(A),\_,\_,\_,\_,R2(B), W2(B)$, in those four blank spaces, we  can put remaining operations, hence, $4!/(2! \times 2!)$

Similarly for Schedules conflict equivalent to serial schedule $T2 \rightarrow T1 .$

Hence, answer 12.

Answer 3

$\color{REd}{T_1\rightarrow T_2}$

$1) $   $R_1(A) \ W_1(A)\  R_1(B)\  W_1(B)\ $$\color{darkblue}{ \ R_2(A)\  W_2(A)\  R_2(B)\  W_2(B)}$

$2) $   $R_1(A) \ W_1(A)\  R_1(B)\ \color{darkblue}{R_2(A)} W_1(B)\ $$\color{darkblue}{ \ \  W_2(A)\  R_2(B)\  W_2(B)}$

$3) $   $R_1(A) \ W_1(A)\ \color{darkblue}{R_2(A)} \  R_1(B)\  W_1(B)\ $$\color{darkblue}{ \ \  W_2(A)\  R_2(B)\  W_2(B)}$

$4) $   $R_1(A) \ W_1(A)\ \color{darkblue}{R_2(A)\ } \  R_1(B) \ \ \color{darkblue}{W_2(A)} W_1(B)\ $$\color{darkblue}{ R_2(B)\  W_2(B)}$

$5) $   $R_1(A) \ W_1(A)\ \color{darkblue}{R_2(A)\ W_2(A)} \  R_1(B) \ \  W_1(B)\ $$\color{darkblue}{  R_2(B)\  W_2(B)}$

$6) $   $R_1(A) \ W_1(A)\  R_1(B)\  \ \color{darkblue}{R_2(A)\ W_2(A)} W_1(B)$$\color{darkblue}{ \  R_2(B)\  W_2(B)}$

$\color{REd}{T_2\rightarrow T_1}$

$6$ schedules : same as above just change of subscript.

Total : $6+6=12$ schedules

Comments

@saxena0612

T1 is coming before T2 right.

then how 6 schedules are possible from T2→T1 ?

we can not right R2(A) before W1(A) similarly for other conflicting pairs of T2 to T1. Isn't it ? 

---

NO, R2(A) can’t come before W1(A) because for being conflict serializable two schedules must follow same order of conflict operations, if R2(A) came before W1(A) schedules will be no longer conflict serializable.

Answer 4

do same for T2----->T1 
and two more Serial Schedule T----->T2, T2----->T1

Two interleaving and two Serial Total four Conflict Serialisable Schedule Possible..

Comments

T1                    T2

R(a)            

                      R(a)

                      w(a)

w(a)

                     R(b)

                     w(b)

  R(b)

  w(b)

This is a conflict schedule na ???? am i wrong if so please correct me

---

no..
R1(A) W2(A) are conflicting pairs, W2(A) W1(A) are conflicting pair..
cycle between R1 & R2 ..

---

The correct answer is 12

But I don't know how 12 is the answer

---

Schedules conflict equivalent to serial schedule $T1 \rightarrow T2 :$

$R2(A) $ must occur after $W1(A),$ and $R2(B)$ must occur after $W1(B)$ and within a transaction, order of operations must remain same, hence,  The only possibility is $R1(A), W1(A),\_,\_,\_,\_,R2(B), W2(B)$, in those four blank spaces, we  can put remaining operations, hence, $4!/(2! \times 2!)$

Similarly for Schedules conflict equivalent to serial schedule $T2 \rightarrow T1 .$

Hence, answer 12.