GATE CSE 2014 | Set 1 | Question: 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)$;

Comments

option d is even serial schedule

---

yes T2 T3 T1

---

option D is corect

becz in D precedencegraph has no cycle

Answer 1

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

Comments

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

Option D is correct bcoz there is no cycle in it

 

Comments

Yes graph needs to be acyclic..

---

Your answer is right but graph drawn is incorrect how did you connected t2 to t3 we only consider when drawing precendence graph this thing 

Two operations conflict if:

✅ same data item
AND
✅ from different transactions
AND
✅ at least one is WRITE.

---

🔥 Conflicts are

Operation pair	Conflict?
R-R	❌
R-W	✅
W-R	✅
W-W	✅

Answer 3

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 4

BEST ANSWER