in Databases retagged by
70,830 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 ______
in Databases retagged by
by
70.8k views

4 Comments

Great man :) Keep it up πŸ‘πŸ».
0
0

@Supriya Priyadarshan best ever explanation

0
0

@Anmol_Binani GOD levelπŸ™πŸ»

0
0

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

I hope this helps!

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

 

1 vote
1 vote
Answer:

Related questions