The Gateway to Computer Science Excellence
+16 votes
2k views

Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

  • $S_1 :r_1(X); r_1(Y); r_2(X); r_2(Y); w_2(Y); w_1(X)$
  • $S_2 :r_1(X); r_2(X); r_2(Y); w_2(Y); r_1(Y); w_1(X)$
  1. Both $S_1$ and $S_2$ are conflict serializable.

  2. $S_1$ is conflict serializable and $S_2$ is not conflict serializable.

  3. $S_1$ is not conflict serializable and $S_2$ is conflict serializable.

  4. Both $S_1$ and $S_2$ are not conflict serializable.

in Databases by Veteran (52.2k points) | 2k views
+1
Also S1: not a view serializable as no blind write present

6 Answers

+24 votes
Best answer

For $S1$ : it is not conflict serializable 

for $S2$ : it is conflict serializable

Answer is option C.

by Boss (30.7k points)
edited by
+8 votes
You can make a Precedence graph for the two schedules.And check for the conflicts pairs making a Cycle.

S1 makes a cycle. T1-->T2 and T2-->T1. And hence is not Conflict Serializable.

S2 does not makes cycle and has transition from T2-->T1 only. And hence is Conflict Serializable.

Conflict Pairs: RW, WR, WW.
by Boss (19.9k points)
0

These WR RW WW are adjacent in the transactions T1 and T2 or any where (in cross or different) in the transaction. please mention. 

+3 votes
Ans - Option C

In S1: RW conflict from 1-2 and 2-1 so It is not C.S.

In S2: RW conflict AND WR conflict from 2-1 only so it is C.S.
by (419 points)
0 votes
As per the precedence graph there is a cycle in schedule S1 T1--->T2 and T2---->T1
 so that's why it is not conflict serializable. 

Schedule S1
   T1            T2
---------------------
  r1(X)
  r1(Y)
                r2(X)
                r2(Y)
                w2(Y)
  w1(X)

Schedule S2
   T1            T2
---------------------
  r1(X)
                r2(X)
                r2(Y)
                w2(Y)
  r1(Y)
  w1(X)
In precedence graph for S2 there is only one edge that is T2--->T1(no cycle) so S2 is conflict serializable
by (307 points)
–5 votes
OPTION IS A
by Junior (593 points)
–5 votes
OPTION IS B IS APPROPIATE ONE
by Junior (593 points)

Related questions

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,645 questions
56,542 answers
195,693 comments
101,534 users