Gate Previous Year Question-2009

Question

I am getting the answer as c but the given answer is b. How b can be ans, there is a cycle R1x->W1x (s1->s2) and W1y->w1y(s2->s1),so s1,s2 can not be conflict serializable…  i m confused.. what is the right answer?

Comments

You can either Google or go to the prev tab and browse all questions from previous year GATE. Or download GO PDF -- http://book.gateoverflow.in

---

thank you.. i just found it in geeks for geeks... i was messing up with schedules and transactions.. i was checking conflict pairs of s2 and s3 where as i should have checked conflict pairs of t1,t2 within s2 and s3 separately... got my mistake.

---

Option c. 

Answer 1

there is no cycle is s2....There is no edge of conflicts between t1->t2 but t2->t1 there...so s2 is conflict serilizable

Answer 2

Step 1: - first  search for  write operation coming in schedule going sequentially

Step 2 : - traverse first left of that Write and Look for following

  i.  Read operation on same data item

  ii. Whether operation is performed by same transaction or not.

    a) If same transaction continue traversing or

    b) if different transaction, draw a edge from reading transaction to writing transaction

iii. Traverse till you reach first operation in reverse sequence and perform step 2.i and 2.ii

Step 3 :- traverse right to the Write operation we selected in previous step and check for same step 2.i and 2.ii on reaching step "2.ii.b" this time draw a edge from writing transaction and to reading transaction

Step 4 :- repeat the steps 2 and 3 with the selected write operation by a particular transaction but this time look for write operation performed by some other transaction on same varialble as our selected transaction.

Step 5. Finally take a look at graph we got. If anywhere in the graph you find cycle its not conflict serializable. If no cycle, its conflict serializable

Hope this helps...