edited by
2,860 views
3 votes
3 votes
Consider the 2 transactions

T1: R(A) W(A) W(B)

T2: R(A) W(A) R(B) W(B)

How many view serializable schedules are possible which are not conflict serializable?

(A) 0

(B) 1

(C) 2

(D) 3
edited by

3 Answers

7 votes
7 votes

Calculating Number of conflict serializable schedules.

 

A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.

We can have to serial schedules $S_1 → S_2$ and $S_2 → S_1$

 

CASE 1. Number of conflict serializabe schedulle that is equivalent to $S_1 → S_2$

Here the colourful arrows represents conflicts, out of these conflicts we can remove the purple arrows since they can be inferred from the diagram.

Rearranging the nodes of the diagram , we get

As we can see the number of conflict serializable schedules possible= toplogical sort possible $= \frac{3!}{2!} = 3$

 

CASE 2. Number of conflict serializable schedule that is equivalent to $S_2 → S_1$

 

Here the colourful arrows represents conflicts, out of these conflicts we can remove the purple arrows since they can be inferred from the diagram.

Rearranging the nodes of the diagram , we get

As we can see the number of conflict serializable schedules possible= toplogical sort possible $= \frac{4!}{2!2!} = 6$

 

$\therefore$ The number of conflict serializable schedules $= 3+6 =9$


Calculating Number of view serializable schedules.

 

A schedule is view serializable if

  1. The Order of initial reads are same as some serial schedule
  2. The Order of W-R conflicts are same as in some serial schedule
  3. The Order of final writes are same as in some serial schedule

 

CASE 1. Number of view serializabe schedule that is equivalent to $S_1 → S_2$

 

Here the colourful arrows represents conflicts, out of these conflicts we can remove the purple arrows since they can be inferred from the diagram.

Rearranging the nodes of the diagram , we get

As we can see the number of view serializable schedules possible= toplogical sort possible $= \frac{3!}{2!} = 3$

 

CASE 2. Number of view serializable schedule that is equivalent to $S_2 → S_1$

 

Here the colorful arrows represents conflicts, out of these conflicts we can remove the purple and green arrows since they can be inferred from the diagram.

Rearranging the nodes of the diagram , we get

As we can see the number of view serializable schedules possible= toplogical sort possible $= \frac{4!}{2!2!} = 6$

 

$\therefore$ The number of view serializable schedules $= 3+6 =9$


$\text{Hence. the number of schedules that are view serializable but not conflict seriable = 9-9=0}$

6 votes
6 votes

 

now we have to calculate the view serializable . and after calculating 

we will get view serializable schedule =9

so difference =9-9=0

edited by
1 votes
1 votes

 

Answer is 3. Each of the below given schedules is view serialisable and not conflict serialisable

 

T1 T2
  R(A)
R(A)  
  W(A)
  R(B)
  W(B)
W(A)  
W(B)  

 

 

 

T1 T2
  R(A)
R(A)  
  W(A)
  R(B)
W(A)  
  W(B)
W(B)  

 

 

T1 T2
  R(A)
R(A)  
  W(A)
W(A)  
  R(B)
  W(B)
W(B)  

 

Related questions

7 votes
7 votes
3 answers
2
Supremo asked Jan 28, 2017
2,133 views
$S: R_1(A),R_2(B),W_2(A),W_3(C),R_4(C),R_3(A),W_3(B),R_4(A),W_2(B),W_4(B),W_3(A)$View serializable or not?
1 votes
1 votes
1 answer
4
shreejeetp asked Dec 14, 2018
294 views
Is every serializable schedule view serializable?, or like conflict serializable, there could be a serializable schedule which isn’t view serializable?