663 views
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 | 663 views
0
is that typo? S1 and S2 should be T1 and T2 under schedule S??
0
It is given like this only.
0
0
answer should be zero. as there are no blind write so no view serializable schedule which is not conflict serializable is possible
0
first read the nitesh joshi comment and after this

@ abhijeet panday

there is a blind write in T1 i.e. W(B)

now conflict serializable  sehedule equivalent to T1->T2 is 3

and  conflict serializable  sehedule equivalent to T2->T1 is 6

so total 9

even though there is a blind write no of view serializable schedule remain =9

0

Gurdeep Saini can you explain me properly ??

0
yes i will post it
0

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

we will get view serializable schedule =9

so difference =9-9=0

by Boss (10.6k points)
edited
0
okay i will check this later on ok ??

btw thanks for you effort
0
0

yeah it's correct thanks  Gurdeep Saini

0
@Gurdeep

How r u checking view serializability.

I think it even cannot be checked. As initial schedule is not there

right?
0
@srestha mam

similar process will be apply to check view serialzable  at this process we have to take care of initial read,write read dependency and final write and we will get 9
0

We found 9 conflict serializable schdules from T1 and T2

To check view serializability ..we should take each of these 9

1) if no blind write ==> not view serializable

2) if blind write ==> draw polygraph and check if cycle

Here in this case as all are view serializable ==> noone has cycle in polygraph

AM i right ???

0

@jatin khachane 1

every conflict serialzable is view serialzable yes this  is true

so the view serialzable will be more then or equal to 9

now i tried  to make VS schedule but not able to make more then 9 and which are already CS

so total differance is 0

now  you told

1) if no blind write ==> not view serializable

no

correct statement is

if schedule is not CS and no blind write  then ==> not view serializable

now i want to tell one more thing

this rule is used when a schedule is given we have to check whether it is view serialzable or not . be careful i am not saying that this rule is wrong

this is true

but here we have to make the VS schedule  from the given transactions so we have to check all possibility  ,

and in all possibility you can apply this rule for checking whether it is view serialzable or not .

now you told

Here in this case as all are view serializable ==> noone has cycle in polygraph

yaa this is true

but there is no need to do so because every CS is VS ,dont make the polygraph and check it again

i hop now you will got what i want to explain

0

Ya got it thanks @

Just check this

Given a set of transactions(ex T1,T2) ..if we have to find # of view serializable/conflict serializable schedules posssible ..we have to find

1) # of schedules view equivalent/conflict equivalent to T1-->T2

1) # of schedules view equivalent/conflict equivalent to T2-->T1

To find # conflict equivalent schedule to any given schedule consider every possibility with Conflicting operation order rule

To find # view equivalent schedule to any given schedule consider every possibility with  1) Same Intial Read 2)Same Final write 3)WR

Now when we are asked for # view serializable schedules..we have find it using view equivalnce definition..coz if we find all conflict serializable shedules there might be some other which are view serializable but not conflct

+1

yes all true

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

@Gurdeep Saini

Is it not view serializable to T1->T2 ..?

If not then why?

Initial read (A) : by T1

Initial read (B) : no one

WR conflict: B T1->T2

Final write(A) : T2

Final write(B ) : T2

But this schedule is having conflict.
If we take T1->T2 serial schedule then also all these 3 will be maintained..

0
it is not view serializable to T1->T2

WR on A is in the serial schedule  but  it is not present in this given schedule ( that is schedule given by you)
0
Is that how we check for view serializable schedules? :/

We try to match the WR conflicts in the given concurrent schedules with the serial one..not in the reverse way right?

+1

We try to match the WR conflicts

not only this we check 3 thing

2) WR

3) final write

in the given schedule

Initial read (A) : by T1

after that we check all the write on A should be same on both schedule

Initial read (B) : no one  yes here you are right

WR conflict: A   T1->T2   you left this one

WR conflict: B T1->T2          yes here you are right

Final write(A) : T2    all the right on A should be before T2

Final write(B ) : T2        all the right on B should be before T2

all this highlighted should be same on both schedule

+1
Thanks I got it.. :)

If two schedules are view equal then their Initial reads, final writes and WR conflicts have to be same..

Was doing a great mistake here :(
0
Nice, thank you:)
0

@Gurdeep Saini

is all that images for only calculating Conflict serializable schedules ?

or it includes calculating View serializables also ?

0
only conflict ,
0

then it may help you to solve for conflict serializable with in 3-5 min https://gateoverflow.in/272638/total-conflict-serializable-schedules#c291462

+1 vote

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)

by (147 points)
0
in all of above 3 example there is no view conflict but they are not serializable to any of the serial schedule T2->T1 and T1->T2
0
It is easy to convert a schedule in serial order T2->T1 under view serializability condition in all of the mentioned schedule.
+1 vote

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}$

by Boss (24.1k points)

+1 vote