21.5k 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 | 21.5k views
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.

+38

### I hope this helps!  +1
This is the best Solution ever
0
Good
0
superb
+3
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!}$.

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$

0
thankss thankss thankss thankss :)

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}$.
by Boss (17.9k points)
edited by
+17

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.

+4
+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 !
0
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

by (193 points)
+1
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

by Boss (16.5k points)
+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.

by (323 points)  For similar type of problems :-

https://gateoverflow.in/247402

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

by Veteran (65.8k points)
+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
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). similary to for

case t2->t1 you will get 6 more

NOTE:

in 12 schedule 2 serial schdeule is also included

by Loyal (6.9k points)
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.

by Boss (13.7k points)
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)

by Boss (10.7k points)
edited