GATE2014-1-29

Question

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by $r(x)$ and $w(x)$ respectively. Which one of them is conflict serializable?

• A. $r_1(x)$; $r_2(x)$; $w_1(x)$; $r_3(x)$; $w_2(x)$;
• B. $r_2(x)$; $r_1(x)$; $w_2(x)$; $r_3(x)$; $w_1(x)$;
• C. $r_3(x)$; $r_2(x)$; $r_1(x)$; $w_2(x)$; $w_1(x)$; 
• D. $r_2(x)$; $w_2(x)$; $r_3(x)$; $r_1(x)$; $w_1(x)$;

Answer 1

(D)  make precedence graph for all the options, for option (D) only graph will be acyclic, hence (D) is CSS.

Comments

Is R - W a conflict ??

---

yup. only R -R is not conflict.

---

R=-W is conflict only when one more read is performed . It is called unrepeatable read. Is it NOt ?

---

Here there is No unrepeatable read in any of the 4 options . Then How can one get cycles in all the graphs . Could some one explain it in a nice manner .

---

take node for evry transaction

procedure is simple scan left to right for 

take first element => scan from 2nd elemnt to right for every r-w . w-w or w-r  conflict in diffrent transaction thier is a edge

take 2nd element => scan from 3rd elemnt to right for every r-w . w-w or w-r  conflict in diffrent transaction thier is a edge

do like this skip left side one elemnt evry time.

if u found cycle then not css otherwise css.

---

@ Arjun Sir,

I wrote D which was given wrong saying correct ans is 4 (GO Full length test). Can you please tell me what to write if similar situation arises in gate exam.

---

@amolagrawal same happened with mebut don't worry this will not happen in gate.

Answer 2

In option D, there is no interleaving of operations. The option D has first all operations of transaction 2, then 3 and finally 1 There can not be any conflict as it is a serial schedule with sequence 2 --> 3 -- > 1

Comments

when we make precedence graph  for option C ,D  only graph will be acyclic, then why option C is not correct ?

---

In option C there is a conflict in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!

---

only  option D is correct as there is no cycle in precedence graph, but in C there is cycle as there are  conflicts in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!

Answer 3

Answer is D