87 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 ______

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

3

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

3

answer is 54. see here for explanation.

http://thegatebook.in/qa/534/the-number-of-conflict-serializable-schedules

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

2

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

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

THANKS...

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

THANKS...

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

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

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

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

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

#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

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

i already share the files on this question, commented

please read complete discussions before commenting it will helps alot

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.

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$

142 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 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}$.

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

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

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?

won't that alter the sequence of T2?

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

@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

0

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

89 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

24 votes

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

@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.

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.

21 votes

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

For similar type of problems :-

2

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

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!

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

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)

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

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

5 votes

answer is 12

similary to for

case t2->t1 you will get 6 more

NOTE:

in 12 schedule 2 serial schdeule is also included

3 votes

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.

2 votes

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)**