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

Wonderfully explained! But there's a small typo in this line :

Obiviously R(B) cant come before W(B) therefore one position.

It should be after.

---

 Tuhin Dutta

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

WILL u pls  explain this ?

---

Please read Sachin Mittal's answer carefully. There cannot be multiple conflict serializable schedules for       T1 -> T2 but only 1 because 

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

Your pic explanation substracts #non-serializing conflict schedules from the total #schedules to get #conflict serializable schedules for the T1 --> T2 case. 

If you see carefully only resource 'y' conflicts for transactions T1 and T2. X is not there in T2 while Z is not there in T1. So no conflict occurs for them. Now we have to calculate all those possible schedules which are non-serializable when W1(Y) or W2(Y) don't run sequentially or serially. So, keeping them fixed in such a position where conflict happens ( the i.e position when they must run serially) as clearly shown in pic, we calculate all possible schedules and subtract that to get actual #conflict serializable schedules. 

Hope you get what I've tried to tell.

---

got it now thnq  Tuhin Dutta

---

@sachin

(note that these W(C) and R(C) cant come before W(B)) in case 1

why?

---

Just a confusion that this procedure of solving will produce the result that is the concurrent schedules which are serializable.. How we get to know the number of conflict or number of view serializable  in this..??

---

but these combinations will also include  W(C) followed by R(C) for T2.

won't that alter the sequence of T2?

---

wonderful explaination !

---

nice exp

but i don not understand why t1 to t2 is not possible

---

Nice explained!!

---

Perfect explanation, but might take few more minutes to solve if related question come in GATE.

---

T1->T2 is a serial schedule...whether we have to consider this as conflict serializable schedule....i think conflict serializable schedules are the non-serial schedules whose result is equivalent to any of the serial schedule comprising of those transaction......

---

Well explanation

---

@Sachin Mittal 1   sir

Very Silly doubt

But important i thnk...While finding Schedules conflcit serializable T2-->T1

It is not necessary that FIRST operation in Schedule should be from T2 only as we are finding equivalent schedules to T2-->T1,

Only Necessary Condition is Conflicting operations should come as T2->T1

Please correct me if i am wrong

---

@jatin
Yes, it should not need to first operation from T2,

---

@Sachin Mittal 1 You're Awesome Sir

---

Yes :)

---

@Sachin Mittal 1 sir..  Can u please explain what will be the number of view equivalent schedules for the same question? Thanks

---

yes you are right @Tuhin Dutta 

But very well explained by @Sachin Mittal 1 sir .

---

what happen if we write t2 and then apply the same procedure??

---

Obliviously R(B)cant come before W(B) therefore one position.

Why? 

And same for R(C) and W(C) actually these can't conflict place any where

---

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.