retagged by
70,732 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 ______
retagged by

18 Answers

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

 

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

edited by
3 votes
3 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)

edited by
Answer:

Related questions

31 votes
31 votes
5 answers
1
Madhav asked Feb 14, 2017
10,827 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\;\text{B}$ , then the maximum order of the B+ Tree is ...
44 votes
44 votes
3 answers
2
Arjun asked Feb 14, 2017
16,029 views
Consider the following database table named $\text{top_scorer}$.$$\overset{\text{top_scorer}}{\begin{array}{|c|c|c|}\hline\\\textbf{player}& \textbf{country}& \textbf...
62 votes
62 votes
6 answers
3
Madhav asked Feb 14, 2017
18,238 views
Consider the following tables $T1$ and $T2.$$$\overset{T1}{\begin{array}{|c|c|c|} \hline \textbf {P} & \textbf {Q} \\\hline \text {2} & \text{2 }\\\hline \text{3} & \te...