GATE CSE 2017 Set 2 | Question: 44

Question

Two transactions $T_1$ and $T_2$ are given as

$T_1:r_1(X)w_1(X)r_1(Y)w_1(Y)$

$T_2:r_2(Y)w_2(Y)r_2(Z)w_2(Z)$

where $r_i(V)$ denotes a $\textit{read}$ operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a $\textit{write}$ operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and $T_2$ is ______

Comments

Great man :) Keep it up 👍🏻.

---

@Supriya Priyadarshan best ever explanation

---

@Anmol_Binani GOD level🙏🏻

Answer 1

There is only one way to have (conflict) serializable schedule as $T1 \rightarrow T2$, because last operation of $T1$ and first operation of $T2$ conflicts with each other.

Now See How many schedules are conflict serializable to $T2 \rightarrow T1$.

I am writing $T1-$

      $R(A)$      $W(A)$         $R(B)$         $W(B)$   
If you notice, I wrote $T1$ with space in between operation.
Now See $T2$ from right, if we see $T2$ from right, then tell me first operation of $T2$ that conflicts with any operation of $T1$.

$W(C)$ and $R(C)$ do not have any conflict with any operation, but $W(B)$ has.

Pick $W(B)$ and see, at how many places it can be there.

Case1:     $\bf{W(B)}$      $R(A)$      $W(A)$         $R(B)$         $W(B)$   
Case2:     $R(A)$        $\bf{W(B)}$    $W(A)$         $R(B)$         $W(B)$   
Case3:     $R(A)$        $W(A)$     $\bf{W(B)}$        $R(B)$         $W(B)$   

Pick each case and see,how many positions other operation of $T2$ can take.

Case1:     $\bf{W(B)}$     $R(A)$      $W(A)$         $R(B)$         $W(B)$   

How many positions $W(C)$ and $R(C)$ can take ?

(note that these $W(C)$ and $R(C)$ cant come before $\bf{W(B)}$)

that is $5C1 + 5C2 = 15$ (either both can take same space or two different spaces)

Now see, for each of these $15$ positions, how many can $R(B)$ take ?

Obviously, $W(B)$ cant come before $R(B),$ therefore one position.

$15 \times 1 = 15$ total possible schedules from case $1.$

Case2:     $R(A)$       $\bf{W(B)}$      $W(A)$         $R(B)$         $W(B)$    

How many positions $W(C)$ and $R(C)$ can take ?

that is $4C1 + 4C2 = 10$ (either both can take same space or two different spaces)

Now see, for each of these $10$ positions, how many can $R(B)$ take ?

Only $2$ positions, because it has to come before $\bf{W(B)}$.

$10 \times 2 = 20$ total possible schedules from case $2.$

Case3:     $R(A)$       $W(A)$      $\bf{W(B)}$        $R(B)$         $W(B)$   

How many positions $W(C)$ and $R(C)$ can take ?

that is $3C1 + 3C2 = 6$

Now see, for each of these $6$ positions, how many can $R(B)$ take ?

Only $3$ positions, because it has to come before $\bf{W(B)}$.

$6 \times 3 = 18$ total possible schedules from case $3.$

total schedules that are conflict serializable as $T2 \rightarrow T1 = 15+20+18 = 53.$

total schedules that are conflict serializable as $T1 \rightarrow  T2 = 1.$

total schedules that are conflict serializable as either $T2 \rightarrow ​​T1$  or  $T1 \rightarrow  T2 = 53+1 = \bf{54}$.

Comments

T1=R(A)W(A)R(B)W(B)
T2=R(A)W(A)R(B)W(B)

How to find number of conflict schedules with the above method?

---

For T1 → T2 conflict serializable, ,

W2(B) can be placed only after W1(B) and R2(B) has to be before W2(B) to be CS acc. to the constraint.(T1 → T2)

Thus,R2(B) W2(B) comes after R1(B)W1(B). For positioning W2(A) there arises 3 cases.

CASE 1: R1(A)W1(A)R1(B)W1(B)W2(A)R2(B)W2(B)

here, R2(A) can be placed in three positions before W2(A) after W1(A) to be conflict serialisable. No. of cases = 3.

CASE 2: R1(A)W1(A)R1(B)W2(A)W1(B)R2(B)W2(B)

here, R2(A) can be placed in two positions before W2(A) after w1(A).

 No. of cases = 2.

CASE 3: R1(A)W1(A)W2(A)R1(B)W1(B)R2(B)W2(B)

here, R2(A) can be placed in one position before W2(A) 

 No. of cases = 1.

Thus, total possible cases = 3+2+1 = 6.

Similarly, you can try for T2 → T1 and add the results with T1 → T2 case to get the answer.

 

---

Step 1:Find all possible serial schedules,in this case it's 2! i.e. T1T2,T2T1.

Step 2:Find all possible conflicts in these 2 serial schedules.

Step 3: Take 2 cases i.e. for T1T2 and T2T1 serial schedules and find possible non serial schedules that have same order of conflicts as the above serial schedules.

For T1T2 there's only one way and for T2T1 we'll get 53 ways.

Answer 2

https://gateoverflow.in/?qa=blob&qa_blobid=15880044459337072929

Easiest Way To Solve.

Find Total number of schedules.

Subtract the non conflict serial schedules from it. Check This

Comments

T1=R(A)W(A)R(B)W(B)
T2=R(A)W(A)R(B)W(B)

How to solve this one with the above method?

---

How to solve the below ques with this method. Help!!
@darshan-at
T1=R(A)W(A)R(B)W(B)
T2=R(A)W(A)R(B)W(B)

---

tx kanha very helpful and intuitive ans

Answer 3

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

For similar type of problems :-

https://gateoverflow.in/247402

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

Comments

how to solve this question by this method please send a screenshot also

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

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

---

@Anuj Sharma

Did you checked the links which are mentioned in the answer ?

Please check them if still you have doubt, comment here.

---

Amazing approach sir!😲

Answer 4

I hope it helps.