retagged by
72,729 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

2 votes
2 votes

If the precedence graph of a schedule is not acyclic then that schedule can't be conflict serializable schedule:

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

 

Answer:

Related questions

31 votes
31 votes
5 answers
9
Madhav asked Feb 14, 2017
10,959 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
10
Arjun asked Feb 14, 2017
16,195 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
11
Madhav asked Feb 14, 2017
18,391 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...