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

Best answer
200 votes
200 votes
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 with 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 ?

Obviously, $W(B)$ cant come before $R(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}$.
edited by
151 votes
151 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

36 votes
36 votes
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,030 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,239 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...