search
Log In
0 votes
183 views

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 183 views
0
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
0
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 there...so s2 is conflict serilizable
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...

Related questions

0 votes
1 answer
2
878 views
T1 T2 T3 R(X) W(X) commit W(X) commit R(X) commit is this transaction conflict serializable and view serializable?
asked Nov 18, 2018 in Databases aditi19 878 views
0 votes
1 answer
3
153 views
T1 T2 T3 W(Y) commit R(X) R(Y) W(Z) commit W(X) commit is this schedule a strict schedule?
asked Nov 18, 2018 in Databases aditi19 153 views
0 votes
0 answers
4
287 views
Tl:W(X), T2:R(X), Tl:W(X), T2:Commit, Tl:Abort is this schedule conflict serializable?
asked Nov 17, 2018 in Databases aditi19 287 views
...