3,046 views

Consider following schedules involving two transactions:

$S_{1}: \: r_{1}(X);r_{1}(Y);r_{2}(X);r_{2}(Y);w_{2}(Y);w_{1}(X)$

$S_{2}: \: r_{1}(X);r_{2}(X);r_{2}(Y);w_{2}(Y);r_{1}(Y);w_{1}(X)$

Which of the following statement is true?

1. Both $S_1$ and $S_2$ are conflict serializable.
2. $S_1$ is conflict serializable and $S_2$ is not conflict serializable
3. $S_1$ is not conflict serializable and $S_2$ is conflict serializable
4. Both $S_1$  and $S_2$ are not conflict serializable

Ans will be C

conflict serializable means we can first run one Transactioon then after it second without any conflict

conflict occurs when data item is same and at least one operation is read

so for S1    r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)

here w1(x) can not be placed before r2(X)  as data item is common(X) and one operation is write so it is not conflict serializable

now for S2   r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)

here r1(X) can be placed after w2(Y) as data item is different and before that only read operation are there so it is conflict serializable as T2 can be executed before T1

S1 is not confllct serializable and S2 is conflict serializable

option 3

There is a slightly mistake in S2: Direction is from 2 --> 1 not 1 --> 2

your second diagram is wrong  in second diagram edge should be from 2 to 1

not from 1 to 2
Yeah it is from 2 ---> 1

S1: here we can see that two confilcting operations r1(y)->w2(y)  and r2(x)->w1(x),so there will be edge from T1 to T2 and T2 to T1 ..so there will be a loop in the graph!So it is not conflict serializable

S2:But here we are not getting such loops in graph for any edge..So it is conflict serialisable

Option C

s1: t1->t2 & t2-> t1 cycle exits

s2t2-> t1 no cycle exits

if cycle -> not conflict serializable