The Gateway to Computer Science Excellence
+19 votes
1.9k views

Consider two transactions $T_1$ and $T_2$, and four schedules $S_1, S_2, S_3, S_4$,  of  $T_1$  and  $T_2$ as given below:

$T_1: R_1[x]W_1[x]W_1[y]$

$T_2: R_2[x]R_2[y]W_2[y]$

$S_1: R_1[x]R_2[x]R_2[y] W_1[x] W_1[y] W_2[y]$

$S_2: R_1[x]R_2[x]R_2[y] W_1[x] W_2[y] W_1[y]$

$S_3: R_1[x]W_1[x]R_2[x] W_1[y] R_2[y] W_2[y]$

$S_4: R_2[x]R_2[y]R_1[x] W_1[x] W_1[y] W_2[y]$

Which of the above schedules are conflict-serializable?

  1. $S_1 \text{ and } S_2$
  2. $S_2 \text{ and } S_3$
  3. $S_3$ only
  4. $S_4$ only
in Databases by Veteran (52.2k points)
edited by | 1.9k views

2 Answers

+24 votes
Best answer

The answer is B.

  • S1 has a cycle from $T1\to T2$ and $T2 \to T1.$
  • S2-- It is uni-directional and has only $T2\to T1.$
  • S3-- It is uni-directional and has only $T1\to T2.$
  • S4-- same as S1.

A schedule is conflict serializable if there is no cycle in the directed graph made by the schedules.

In the schedules we check for RW, WR, WW conflicts between the schedules and only these conflicts contribute in the edges of the graph.

by Boss (19.9k points)
edited by
–2
Ans will be c because
0
no. it's b) you can check it by precednce graph.
0
Thanks @Sandeep for correction
0
I got the answere by drawing schedules but why T1 and T2 is given...??
0
to describe what belongs to T1 and wat to T2
+1 vote

option b

by Boss (36.7k 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
50,737 questions
57,370 answers
198,506 comments
105,276 users