Register

GATE CSE 2017 | Set 2 | Question: 44

• retagged by
116,461 views
242 242 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 ______

25 Answers

Best answer
278 278 votes

There is only one way to have (conflict) serializable schedule as T1 → 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 → 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:     W(B)      R(A)      W(A)         R(B)         W(B)
Case2:     R(A)        W(B)    W(A)         R(B)         W(B)
Case3:     R(A)        W(A)     W(B)        R(B)         W(B)

Pick each case and see how many positions other operation of T2 can take.

Case1:
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) can't come before W(B))

That is 5C1 + 5C2 = 15

Now see, for each of these 15 positions, how many can R(B) take?
Obviously, W(B) can’t come before R(B), therefore one position.

15 × 1 = 15 total possible schedules from case 1.

Case2:
R(A)       W(B)      W(A)         R(B)         W(B)

That is 4C1 + 4C2 = 10
Only 2 positions for R(B)

10 × 2 = 20 total possible schedules from case 2.

Case3:
R(A)       W(A)      W(B)        R(B)         W(B)

That is 3C1 + 3C2 = 6
Only 3 positions for R(B)

6 × 3 = 18 total possible schedules from case 3.

Total schedules conflict serializable as T2 → T1 = 15 + 20 + 18 = 53

Total schedules conflict serializable as T1 → T2 = 1

Total conflict-serializable schedules (either direction) = 53 + 1 = 54

• edited by
214 214 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

52 52 votes
36 36 votes

If there are n transactions and each having operations a1,a2,a3,.....an. then 

Total number of schedules possible = $\frac{(a_{1}+a_{2}+a_{3}+...+a_{n})!}{a_{1}!a_{2}!a_{3}!...a_{n}!}$

Therefore, for this question, total schedules possible = $\frac{(4+4)!}{4!4!}=70$

Lets find Schedules which can form cycle in the precedence graph i.e the schedules which are non-serializable.

For operations to be conflicting atleast one of them should be write operation.

Conflicting operations form cycle in two ways for given transactions.

Now, we can apply above formula to find the schedules possible for above two cases as shown below ( We fix W2(Y) in first case and W1(Y) in second case).

Total non-serializable schedules possible = 12 + 4 = 16.

Therefore, serializable schedules possible = 70 - 16 = 54.

Answer: 54

 

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

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2017 | Set ...Next → · combinatorics
← Previous in category · GATE CSE 2017 | Set ...Next in category → · GATE 2017
Position:
Show:

Related questions

0 0 votes
0 0 answers
326
326 views
Balaji Jegan asked Oct 23, 2018
326 views
TANCET 2017 SERIALIZABILITY
33 33 votes
3 answers 3 answers
17.1k
17.1k views
Arjun asked Feb 18, 2021
17,093 views
GATE CSE 2021 | Set 2 | Question: 32
​​​​​Let $S$ be the following schedule of operations of three transactions $T_1$, $T_2$ and $T_3$ in a relational database system:$$R_2(Y), R_1(X), R_3(Z), R_1(Y)W_1(X), ...
88 88 votes
4 answers 4 answers
45.1k
45.1k views
go_editor asked Sep 28, 2014
45,085 views
GATE CSE 2014 | Set 2 | Question: 29
Consider the following schedule S of transactions $T1, T2, T3, T4:$$${\begin{array}{|l|l|l|l|}\hline\textbf{T1}& \textbf{T2}& \textbf{T3}& \textbf{T4} \\\hline& \...
26 26 votes
3 answers 3 answers
11.9k
11.9k views
Arjun asked Feb 18, 2021
11,911 views
GATE CSE 2021 | Set 1 | Question: 32
Let $r_i(z)$ and $w_i(z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_i$. Consider the following two schedules.$S_1: r_1(x)r_1(y)...