5,864 views
6 votes
6 votes
Consider the following orders of transactions:

T2:R(x); T3:W(x); T3:commit; T1:W(x); T1:commit; T2:R(y); T2:W(z); T2:commit; T4:R(x); T4:R(y); T4:commit.

If S is serializable, then how many conflict serial orderings of S is possible?

(A)10

(B)11

(C)8

(D)13

2 Answers

Best answer
12 votes
12 votes
selected by
0 votes
0 votes
$T_{1}$ $T_{2}$ $T_{3}$ $T_{4}$
$1.$      
$2.$ $r(x)$    
$3.$      
$4.$   $w(x)$  
$5.$      
$6.$   $Commit$  
$7.$      
$8.$ $w(x)$      
$9.$      
$10.$ $Commit$      
$11.$      
$12.$ $r(y)$    
$13.$      
$14.$ $w(z)$    
$15.$      
$16.$ $Commit$    
$17.$      
$18.$     $r(y)$
$19.$      
$20.$     $Commit$
       

Now, See for $T_{2}$ $r(y)$ , $w(z)$ , $Commit$ has no conflict with $T_{1}$ or $T_{3}$. So, $T_{2}$ can be placed in $3,5,7,9,11$ th places. Now all 3 of them can be placed in 1 place , or 2 place in one among these 5 places and 3rd one in another place , or all 3 can place in different place

So, $\binom{5}{1}+\binom{5}{2}+\binom{5}{3}=25$ arrangement are possible

-------------------------------------------------------------------------------------------------------------------------

Now, Similarly $T_{4}$ can arrange in 8 places. Now, $T_{4}$ transaction can place $\binom{8}{1}+\binom{8}{2}=36$ ways

So, total arrangement $25+36=61$ ways

edited by

No related questions found