test series

Question

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

Comments

srestha mam

conflict serializable should be more

but conflict equivalent such a less number I think

what I know that  both  conflict equivalent and conflict  serializable are the same thing ??? 

correct me if I'm wrong

 

---

@Magma

if those are same things, why my page-2 answer not match with page-1 answer ( in the images of answer.)

 ( you already know it just recall from  https://gateoverflow.in/96108/schedules )

Moreover mam, written that statement wrongly,

actual sentence is

conflict serializable schedules ≤ conflict equivalent schedules

---

hmmm thanks Shaik Masthan

Answer 1

for clarity images https://drive.google.com/open?id=1C3NO8gDGdRzUn5JHY6bj3ptQLHEruUi4

Comments

@Shaik Masthan  Sir,

So answer to this question will be 1 & Not 8 as per your last comment  ??

$T_{2}$$\rightarrow$$T_{3}$$\rightarrow$$T_{1}$$\rightarrow$$T_{4}$

---

@Kushagra गुप्ता

yes, but note that there are 14 more conflict equivalent schedules which are conflict equivalent to other schedules.

---

What about the 2nd part of the ans  @Shaik Masthan?

Answer 2

$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

Comments

check this question https://gateoverflow.in/96108

to understand between the terms conflict serializable schedule and conflict serializable serial schedule

---

conflict serializable schedule can't be greater than n! (n is no. of transaction)

no.of  conflict serializable schedule can be greater than n! (n is no. of transaction)

ex:- T1 have R(A),W(A) and T2 have R(B),W(B)

serial schedules are = 2! = 2 ===> 1) T1 ---> T2 and 2) T2 ---> T1

conflict serializable schedules = $\frac{4!}{2!\;.\;2!} = 6$, in this 6 schedules, 3 are conflict serializable to the serial schedule T1 ---> T2 and remaining 3 are conflict serializable to the serial schedule T2 ---> T1.

---

@ Shaik Masthan  yeah you are right ,CSS can be greater than n!,i did mistake.thank you.