in Databases retagged by
70,831 views
150 votes
150 votes
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 ______
in Databases retagged by
by
70.8k views

64 Comments

edited by
2
2
I think 4
0
0
I was getting as 12

T1 to T2 only one serial

T2 to T1 10 concurrent and 1 serial

Total 12.
1
1
edited by

This question is exactly same here 

But I'm not totally satisfied with the solution

6
6
moved by
https://gateoverflow.in/26891/number-of-conflict-serializable-schedules same question  answer is 54.  nicely explained.
3
3
edited by
3
3
edited by

Video Explanation: 

5
5
can anyone explain it better??
1
1
video doesnt have a clear solution
4
4

(a) R1(X) (b) W1(X) (c) R1(Y) (d) W1(Y) (e)

The (a)...(e) represents the slots that can be filled in by operations from transaction 2. For convenience number the operations sequentially from (1) to (4) for operations in T2. Now, let (1) go to (a). For a conflict causing schedule, (2) must go to (d) or (e). After that fixing (3) is placed based on whether (2) goes to (d) or (e). Representing this:

This would be the situation every time (1) is placed at any position i.e. (a)..(d). Note that there wouldn't be a conflict if (1) is placed at (e). Hence we would have 4 positions for a, giving rise to 4 positions. The path to each leaf represents a way to place (2),(3) and (4). Hence in total $4\times4 = 16$ possibilities of conflicts. Subtracting from the total number of schedules we would get $70-16=54$. 

7
7
Good observation @Krish. This is the beauty of PnC problems.Variety of good solutions:) Add it as an answer
0
0

easy solution

82
82
I can't find simpler than this....

I didn't understand any method.. except this.. BEST ANSWER I COULD FIND.

THANKS...
3
3
Welcome :)
0
0

If the Precedence graph of a schedule is not $acyclic$ then, that schedule is not conflict serializable schedule and it is not conflict equal to any of the serial schedule:

There are only possible two serial schedules $T1 -> T2$ and $T2 -> T1$ so a conflict serializable schedule should  be conflict equal to either of the serial schedule:

6
6
edited by

I agree with ramana reddy ...

Thank you so much for providing such an easy solution  Anmol_binani

sharing one more link if it helps :  http://thegatebook.in/qa/534/the-number-of-conflict-serializable-schedules

1
1
reshown by
can anyone please explain with proper logic why { r1(y) | w2(y) | w1(y) } is not possible OR {  r2(y) | w1(y) | w2(y)  } is not possible?

there is no fixed schedule given in question for any of the transactions then why this is not possible?

I know about the conflicts RW WW WR , but what is the logic on the basis of which people are saying [ r1(y) w1(y)] and [r2(y)w2(y)] has to be performed together, there cant be any interleaved OTHER operation or any CONTEXT SWITCH between these two combination !!!

What is the logic behind it? please anyone expplain.. it will be a great help!!

may be the question is silly to you .. but i am not getting the logic... if possible pls help anyone !!!

Rest of the solution i understood :-(
0
0
Could you explain case 1 and case 2 more precisely ? I am not able to understand it how it forms.
0
0
Tell me exactly where is your confusion ? i will try to help you
0
0
How to think of case 1 and case 2 ?We need to take non conflicting actions .So there are so many non-conflicting actions there . I am not able to understand the procedure .Plz explain.
0
0

ashwina

you have to think in the opposite way, i.e., think of the conflicting actions and subtract them from total possible schedules.

0
0

@puja .. Problem is pretty straight forward and clearly explained and in my limited knowledge i dont find anything wrong with this approach.

0
0
I think Extended discussion can be carried below the answer.Otherwise looking at the answer,one need to scroll a lot.
2
2
Still nt able to understand ... wats wrong with that video ?? anyone ??

#rahul if comments r discussion then no problem in scrolling =D ...
0
0
@krish...why there won't be any conflict if we place 1 at (e)???Only this point I am not able to understand..
0
0
@Puja, that explanation is absolutely correct.
0
0
can u tell me wats wrong with the video i posted ....
0
0
I didn't feel anything is wrong with the solution procedure given by Techtud.
0
0
The video i posted .... is it ok according to this question ??
0
0
Yes, it is.
0
0
then y 12 is not the answer of this question ??
0
0

Sorry Puja I misunderstood your previous post. I thought of the same video posted by Smartmeet.

Now the question itself is wrong in the video you posted.

T1: R1(A) W1(A) R2(B) W2(B) 

The portion in bold cannot happen since the transaction is T1. They can only occur in transaction T2.

In this GATE question the schedule T1 ----> T2 can be arranged in only 1 way since the last operation of T1 and the first operation of T2 are conflicting while if I consider the question in the video you posted there is no such conflicting scenario. So for these kinds of problems you have to identify the conflicting operations and then arrange accordingly.

0
0

I hope this helps!

68
68
This is the best Solution ever
3
3
Good
0
0
superb
0
0
3
3

The best answer anyone could refer thanks yar @Anmol_Binani.

0
0
In the last case T1 -> T2 how there is only one possibility?
0
0

i already share the files on this question, commented

please read complete discussions before commenting it will helps alot

0
0
Best one!!
0
0

@Shamim Ahmed

i added one more approach as answer, if you want you may check it !

0
0
Got it! Thanks bhai..
1
1
The only solution I understood ... Thanks
0
0

@Supriya Priyadarshan Thank you for this wonderful solution. I have been trying to solve it for an hour almost . Only now i could understand.

0
0
Great approach
0
0

@Anmol_Binani

Why you wrote $\dfrac{3!}{3!}$ int the last. I mean why we need to divide by $\mathbf{3!}$.

0
0

$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$

4
4
thankss thankss thankss thankss :)
0
0
Thanks
0
0
Thanks for the best explanation
0
0
This question was a nightmare
3
3
4
4
Tag it hard
3
3

This solution is really nice and understandable. but I have a doubt here in this question conflict is happening due to only Y data items but if more than one data item there who creating conflict then how we do. for example in this question?  @ANMOL_BINANI

 

1
1
(A) 2
1
1
Anmol bhai jindabad ;)
2
2
edited by
Best way to solve this question in exam is don’t solve it very early. Because such a complex question in early phase of GATE paper degrade the confidence exponentially & even if you are able to solve it then also it will cost a time of 4-5 one marks questions. Anyway at the end of the day marks decide rank not questions which you solve!

But while solving PYQ analyze it thoroughly
1
1
edited by

Aliter :

4
4
God bless u you helped me a lot 🙏
1
1
Great man :) Keep it up 👍🏻.
0
0

@Supriya Priyadarshan best ever explanation

0
0

@Anmol_Binani GOD level🙏🏻

0
0

18 Answers

200 votes
200 votes
Best answer
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}$.
edited by

4 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?
0
0

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.

 

0
0
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.
1
1
151 votes
151 votes

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

4 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?
0
0
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)
0
0
tx kanha very helpful and intuitive ans
0
0
36 votes
36 votes

4 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)
0
0

@Anuj Sharma

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

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

0
0
Amazing approach sir!😲
1
1
30 votes
30 votes

I hope it helps.

Answer:

Related questions