TOTAL CONFLICT SERIALIZABLE SCHEDULES

Question

Two transactions T1 and T2 are given as

T1:r1(A) w1(A) r1(B) w1(B) r1(C) w1(C)

T2:r2(B) w2(B) r2(C) w2(C) r2(D) w2(D)

The total number of conflicts serializable schedules that can be formed by T1 and T2 are _____

Answer 1

Before Solving this question, it is recommended to have a look on https://gateoverflow.in/247402

for clarity images https://drive.google.com/open?id=1SUxBvjlo3XvA0EcWBEDPwDMtxcI3PNXy

Comments

D->E conflict? @Shaik it is same transaction, rt?

Plz think little bit

---

D -> E not a conflict, but mam, in a transaction, order of operations should be preserved !

due to that reason D --> E is present !

( in your answer on this question, you are also doing the same and getting 6 as t1 -> t2 )

---

thanku @shaik sir for introducing  this approach for avg. person like me and many others who find combinatory tough

Answer 2

In $T_{1}\rightarrow T_{2}$

$T_{1}$	$T_{2}$
$r(A)$
$w(A)$
$r(B)$
$w(B)$
${\color{DarkRed} {r(C)}}$
${\color{DarkRed} {w(C)}}$	${\color{DarkRed} {r(B)}}$
	${\color{DarkRed} {w(B)}}$
	$r(C)$
	$w(C)$
	$r(D)$
	$w(D)$

 

Here those colored $4$ transaction has no conflict

So, Number of conflict will be $=\frac{4!}{2!2!}=6$

We divided by $2!$ because $r(C),w(C)$ cannot combine among them

Similarly $r(B),w(B)$ cannot arrange among them.

---

Now for $T_{2}\rightarrow T_{1}$

Case $1:$

$r1(A),w1(A)$ has no conflict with any transaction of $T_{2}$

So, total conflict serializable schedule$=\frac{8!}{2!6!}=28$

Now for $r1(B),w1(B)$ has no conflict with $r2(C),w2(C)$,$r2(D),w2(D)$ of $T_{2}$

So, total conflict serializable schedule$=\frac{6!}{2!4!}=15$

Now for $r1(C),w1(C)$ has no conflict with $r2(D),w2(D)$

So, total conflict serializable schedule$=\frac{4!}{2!2!}=6$

---

Total number of conflict serializable schedule$=6+28+15+6=55$

Comments

mam, i added the answer, you may check it !