Test by Bikram | Databases | Test 1 | Question: 5

Question

Two transactions of $T1$ and $T2$ are given as follows:
$T1: \text{R1(A) W1(A)  R1(B)  W1(B)}$
$T2 : \text{ R2(B) W2(B)  R2(C)  W2(C)}$

Total number of Conflict Serializable schedules  formed by $T1$ and $T2$ are

• A. $2$
• B. $70$
• C. $54$
• D. $12$

Comments

Is there any other method to solve this?

---

i think not , you can follow this 

https://gateoverflow.in/26891/number-of-conflict-serializable-schedules

Answer 1

according to reference of given link, nswer should be 54. how answer is 7?

https://gateoverflow.in/26891/number-of-conflict-serializable-schedules

Comments

that would be 54 not 5 and 70 not 7, corrected

thanks.

---

I guessed answer for this question :P :P total concurrent possible schedules are 70 (^m+nC_n) and I am sure all are not CSS, and 54 is closer value to 70 which is the correct answer! 

Answer 2

$T1\rightarrow T2$

Because of $W_{1}(Y)$ and $R_{2}(Y)$ conflict there is one serializable schedule which is also a serial schedule.

$T2\rightarrow T1$

$R_{2}(Y)$ $W_{2}(Y)$ $R_{2}(Z)$ $W_{2}(Z)$ $\rightarrow$ $R_{1}(X)$ $W_{1}(X)$ $R_{1}(Y)$ $W_{1}(Y)$

Let's assume $R_{2}(Z)$ $W_{2}(Z)=Q$ and $R_{2}(Z)=M$ and $W_{2}(Z)=N$

$\underbrace{R_{1}(X)W_{1}(X)}$ $R_{2}(Y)$ $W_{2}(Y)$ $Q$ $R_{1}(Y)$ $Q$ $W_{1}(Y)$ $Q=3$

$\underbrace{R_{1}(X)W_{1}(X)}$ $R_{2}(Y)$ $W_{2}(Y)$ $M$ $R_{1}(Y)$ $N$ $W_{1}(Y)=1$

$\underbrace{R_{1}(X)W_{1}(X)}$ $R_{2}(Y)$ $W_{2}(Y)$ $M$ $R_{1}(Y)$ $W_{1}(Y)$ $N=1$

$\underbrace{R_{1}(X)W_{1}(X)}$ $R_{2}(Y)$ $W_{2}(Y)$  $R_{1}(Y)$ $M$ $W_{1}(Y)$ $N=1$

$Total =6$

$R_{2}(Y)$ $\underbrace{R_{1}(X)W_{1}(X)}$ $W_{2}(Y)$ $Q$ $R_{1}(Y)$ $Q$ $W_{1}(Y)$ $Q=3$

$R_{2}(Y)$ $\underbrace{R_{1}(X)W_{1}(X)}$ $W_{2}(Y)$ $M$ $R_{1}(Y)$ $N$ $W_{1}(Y)=1$

$R_{2}(Y)$ $\underbrace{R_{1}(X)W_{1}(X)}$ $W_{2}(Y)$ $M$ $R_{1}(Y)$ $W_{1}(Y)$ $N=1$

$R_{2}(Y)$ $\underbrace{R_{1}(X)W_{1}(X)}$ $W_{2}(Y)$  $R_{1}(Y)$ $M$ $W_{1}(Y)$ $N=1$

$Total=6$

$R_{2}(Y)$ $W_{2}(Y)$ $Q$ $\underbrace{R_{1}(X)QW_{1}(X)}$ $Q$ $R_{1}(Y)$ $Q$ $W_{1}(Y)$ $Q=5$

Similarly start putting M and N, you will get $10$ more ways.

$Total=15$

$\underbrace{R_{1}(X)}$ $R_{2}(Y)$ $\underbrace{W_{1}(X)}$ $W_{2}(Y)$ $Q$ $R_{1}(Y)$ $Q$ $W_{1}(Y)$ $Q=3$

Similarly start putting M and N, you will get $3$ more ways.

$Total=6$

$\underbrace{R_{1}(X)}$ $R_{2}(Y)$ $W_{2}(Y)$ $Q$ $\underbrace{W_{1}(X)}$ $Q$ $R_{1}(Y)$ $Q$ $W_{1}(Y)$ $Q=4$

Similarly start putting M and N, you will get $6$ more ways.

$Total=10$

$R_{2}(Y)$ $\underbrace{R_{1}(X)}$ $W_{2}(Y)$ $Q$ $\underbrace{W_{1}(X)}$ $Q$ $R_{1}(Y)$ $Q$ $W_{1}(Y)$ $Q=4$

Similarly start putting M and N, you will get $6$ more ways.

$Total=10$

$Finally\ for\ T2\rightarrow T1=6+6+15+6+10+10=53$

$Ans: 54$