The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
2.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 (112k points) | 2.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 (41.6k points)
edited 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 .
+6

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!
–1 vote
Answer is D
answered by Loyal (8.8k 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

44,455 questions
49,911 answers
165,378 comments
65,897 users