The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
2k views

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?

  1. $r_1(x)$; $r_2(x)$; $w_1(x)$; $r_3(x)$; $w_2(x)$;
  2. $r_2(x)$; $r_1(x)$; $w_2(x)$; $r_3(x)$; $w_1(x)$;
  3. $r_3(x)$; $r_2(x)$; $r_1(x)$; $w_2(x)$; $w_1(x)$; 
  4. $r_2(x)$; $w_2(x)$; $r_3(x)$; $r_1(x)$; $w_1(x)$;
asked in Databases by Veteran (103k points) | 2k views

3 Answers

+17 votes
Best answer

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

answered by Boss (40.5k points)
edited ago by
0
Is R - W a conflict ??
0
yup. only R -R is not conflict.
0
R=-W is conflict only when one more read is performed . It is called unrepeatable read. Is it NOt ?
0
Here there is No unrepeatable read in any of the 4 options . Then How can one get cycles in all the graphs . Could some one explain it in a nice manner .
+5

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.

0
@ 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.
0
@amolagrawal same happened with mebut don't worry this will not happen in gate.
+3 votes
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
answered by (263 points)
0
when we make precedence graph  for option C ,D  only graph will be acyclic, then why option C is not correct ?
0
In option C there is a conflict in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!
+3
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!
0 votes
Answer is D
answered by Loyal (8.5k points)
Answer:

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

41,053 questions
47,651 answers
147,206 comments
62,380 users