# GATE2017-2-44

30.7k views
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 ______

retagged
2
0
I think 4
1
I was getting as 12

T1 to T2 only one serial

T2 to T1 10 concurrent and 1 serial

Total 12.
6

This question is exactly same here

But I'm not totally satisfied with the solution

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

Video Explanation:

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

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

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

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

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

THANKS...
0
Welcome :)
5

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: 0

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

0
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
Could you explain case 1 and case 2 more precisely ? I am not able to understand it how it forms.
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

ashwina

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

0

Can anyone tell me wats wrong with this approach ???

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

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

#rahul if comments r discussion then no problem in scrolling =D ...
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
@Puja, that explanation is absolutely correct.
0
can u tell me wats wrong with the video i posted ....
0
I didn't feel anything is wrong with the solution procedure given by Techtud.
0
The video i posted .... is it ok according to this question ??
0
Yes, it is.
0
then y 12 is not the answer of this question ??
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.

45

### I hope this helps!  3
This is the best Solution ever
0
Good
0
superb
0

The best answer anyone could refer thanks yar

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

i already share the files on this question, commented

0
Best one!!
0

@Shamim Ahmed

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

1
Got it! Thanks bhai..
0
The only solution I understood ... Thanks
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
Great approach
0

@Anmol_Binani

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

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$

0
thankss thankss thankss thankss :)
0
Thanks for the best explanation

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

Obliviously $R(B)$ cant come before $W(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
19

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.

2

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.

0

got it now thnq  Tuhin Dutta

0

@sachin

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

why?

0
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..??
0
but these combinations will also include  W(C) followed by R(C) for T2.

won't that alter the sequence of T2?
1
wonderful explaination !
1
nice exp

but i don not understand why t1 to t2 is not possible
0
Nice explained!!
0
Perfect explanation, but might take few more minutes to solve if related question come in GATE.
0
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......
0
Well explanation
0

@   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

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

@Sachin Mittal 1 You're Awesome Sir

0
Yes :)
0

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

0

yes you are right

But very well explained by @Sachin Mittal 1 sir .

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

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

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

2
0
great answer ... I could come halfway till thinking about total serial schedules and total conflict situation....nice ans..this helped....what to do if this type of questions comes
0
Nice explanation  @ kanha95
0
Thanks, very good explaination.
0
this is wow!!
0
nice thanks a lot

T1 : R1(A) W(A) R1(B) W1(B)
1         2        3       4
↙

T2 : R2(B) W2(B) R2(C) W2(C)
5         6          7         8
Conflict condition RW WR WW
There are total 5 conflict operation
1. T(1) & T(2) operations should execute in given ordered sequence
1-2-3-4 and 5-6-7-8
2.NO operation should come between any two conflict schedule operation e.g. between 5 and      6 no other operation can come otherwise it will violate the condition.

Let us count how many combination can be made from given condition-:

1) Execute all T(1) first then T(2)
i.e.   1-2-3-4-5-6-7-8              ----------------- 1 way
2)Since there is conflict between 3 and 6 so we can say that 6 should execute before 3 to avoid violation.
6<3
To count this first let us count how many total concurrent process can  be possible .

__5__6__7__8__
so we have 5 empty space out which we have to fill with 4 operation (1,2,3,4) with repetition.
At each empty space any number of operation can come.
It is similar problem to chocolate problem.

Total Number of concurrent process =
(5+4-1)C4 = 70
(n=5(empty space)     r=4(total operation)  therefore (n+r-1Cr) )

But this also include in which our condition are violating.  6

1) 1 2 3 4 occur before 6
here n= 2 r =4
therefore (2+4-1)C4 = 5

2) 1 2 3 occur before 6
here n= 2 r= 3
therefore (2+3-1)C3 =  4 but here d can be at 3 place  so total 4 *3 = 12 arrangement

so total 12 +5 = 17 arrangement are violating our condition out 0f 70 concurrent arrangement
So total arrangement = 70 -17 = 53

So total arrangement = serial arrangement + concurrent arrangement
= 53 + 1 = 54

1
But we check conflict sequence in two different transactions..for example in given question 4-5 and 4-6 is a conflict..we cant consider conflict in the same transaction that is the only rule!
1
why are u taking the case that 6 should come before 3..even 3 can come before 6..why are u nt taking that case?or 4 should be performed before 5
0
n>r in combination
1
I am really not getting this procedure..anyone please explain it in simplified [email protected]
1
Is their any particular way to solve number of conflict equivalent schedule??
0
@Bikram sir,

In this the intra Transaction precedences of operations are changing like:-

5 2 1 6 7 8 3 4

in this 1 should execute before 2.

But such kind of transactions is also included in this count.
0

how any number of operation can come if there are only 1,2,3,4 given once ..how can they repeat .?

1,2,3,4_______5_____1,2,3,4__6___ 1,2,3,4____7__1,2,3,4___8______

you mean like this ?

plz explain..

0
nice explaination'
3
How did you answer in 2015 when it was asked in 2017? :O I hope it helps.  For similar type of problems :-

https://gateoverflow.in/247402

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

2
Nice explaination!

Btw in DAG for T2 → T1, for V and W, you misswrote R1(B), W1(B) as R2(A), W2(A).
0
Hooooo... But now i can't update the image !
0
No problem brother...all that matters is the method & that was perfect
0

@Shaik Masthan it means you are trying to make DAG for by fixing v at different positions right ?

0
yes brother
0

@Shaik Masthan Thanks brother! This method is simpler and faster!

0
awesome brother ..really very helpful to me..
0
awesome
0

@Shaik Masthan sir, instead of conflict serializable schedules if the question would have been number of schedules which are conflict equal to S then will the answer remain the same or different?

0
To some S?

then answer will depend upon S but not same as the above
0

to this schedule S. And what should be the approach to solve such a question?

0
Where is schedule S?
0
oh sorry i meant to the above given transactions sir
0
Hi Sir,

Why P --> W conflict is not shown. Although the approach used by you is the best of all answers  I have read. But I really can't make out when to leave out some conflicts. Like in this question actually there are three conflicts in T2 --> T1 -- R2(B)--> R1(B), W2(B) --> R1(B), W2(B) --> W1(B). But only once conflict is included W2(B) --> R1(B). I am really confused. Any help will be really appreciated. I have spent 3 hours but my brain is just not getting the logic. Also how is this formula calculated - any reference - (2+2)!/2!2!
0
Pardon, The third conflict is R2(B) --> W1(B).
0
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

@Anuj Sharma

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

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

case t2->t1 you will get 6 more

NOTE:

in 12 schedule 2 serial schdeule is also included

0

can u solve this question plzz..am getting 6 for this but answer is given 7 in one place and 14 in one place 0
Only 2 conflict serializable schedule is possible
 1 r(x) A r(y) 2 w(x) B w(y) 3 r(y) C r(z) 4 w(y) D w(z)

Total number of schedules will $\frac{8!}{4!*4!}$ = 70

OR

We have to place 4 items(A,B,C,D) in five buckets (_1_2_3_4_ ) = $\binom{5+4-1}{4}$ = 70

But all of them are not conflict serializable schedules  so we will substract  non conflict serializable schedules

Non conflict serializable schedules are  = A1_2_3(BCD4) + _1A2_3(BCD4) + _1_2A3(BCD4) + _1_2_3A(BCD4) = $4*\binom{3+2-1}{1}$ = 16

So total number of conflict serializable schedules are = 70 -16  = 54.

Thank you @krish__ ji.

I think testing given schedule is view serializable is NP Problem but testing given schedule is conflict  serializable is P problem.

But  finding all view/conflict serializable schedules is NP problem. Please correct me if i am wrong.

edited by

Solved in a direct way.

#ways in which 'N' objects can be divided into K partitions where any partition can get any num including 0 is given by

C( N+K-1, K-1),  where N = objects & K =partitions

#          a       b         c        d                                          1         2         3       4

T1:  R(A)  W(A)  R(B)  W(B)                              T2:  R(B)  W(B)  R(C)  W(C)

Constraints we need to follow while making conflict serializable schedules for the above transactions are :

1) For T1: a < b < c < d ( Here '<' means "comes before")

2) For T2: 1 < 2 < 3 < 4

3) When T1 < T2:  d < 1         Since there are two conflicts of d. One with 1 (WR case) and another with 2 (WW case).Apart from this constraint, we must satisfy 1) & 2) constraints too for building conflict serializable schedules.

4) When T2 < T1:  2 < c        Since there is one conflict of c with 2. Apart from this constraint, we must satisfy 1) & 2) constraints too for building conflict serializable schedules.

T1 < T2: Only one schedule exists!  a b c d 1 2 3 4

T2 < T1: Three cases exists, arranging with reference to this structure  _1_2_3_4_. All the blanks are partitions which can hold any no of items.(including 0)

a < b < 2 < c < d:  For a < b < 2,  N = 2; K =2; C( 2+2-1,2-1) = C(3,1) = 3.

For 2 < c < d, N =2; K =3; C(2+3-1, 3-1) = C(4,2) = 6

Thus 6 * 3 =18

a < 2 < b < c < d:  For a < 2, N = 1; K = 2; C( 2+1-1,2-1) = C(2,1) = 2

For 2 < b < c < d. K = 3; N = 3; C(3+3-1,3-1) = C(5,2) = 10

Thus 10 * 2 = 20

2 < a < b <  c < d: K = 3; N = 4; C(4+3-1,3-1) = C (6,2) = 15

So, T2 < T1 has 18 + 20 + 15 = 53 arrangements and T1 < T2 has 1 arrangement. Thus total 54(ans)

edited

## Related questions

1
5.1k views
In a B+ Tree , if the search-key value is $8$ bytes long , the block size is $512$ bytes and the pointer size is $2$ B , then the maximum order of the B+ Tree is ____
Consider the following database table named $\text{top_scorer}$ ... > ANY (SELECT tc.goals FROM top_scorer AS tc WHERE tc.country='Germany') The number of tuples returned by the above SQL query is ______
Consider the following tables $T1$ and $T2.$ ... cascade. In order to delete record $\langle 3, 8 \rangle$ from the table $T1,$ the number of additional records that need to be deleted from table $T1$ is _______