The Gateway to Computer Science Excellence
0 votes

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?

in Databases by (287 points) | 98 views
You can either Google or go to the prev tab and browse all questions from previous year GATE. Or download GO PDF --
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.

2 Answers

0 votes
there is no cycle is s2....There is no edge of conflicts between t1->t2 but t2->t1 s2 is conflict serilizable
by (105 points)
0 votes
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...
by (23 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
104,698 users