Awesome q2a theme
0 votes
26 views
What is the difference between number of schedules which are conflict equal to S and number of serial schedules which are conflict equal to S? Can anybody show an example of the same ? This is very confusing.
in Databases by (120 points) | 26 views

1 Answer

+1 vote

S$_{1}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), R$_{2}$(Y), W$_{1}$(Y), W$_{2}$(Y)

S$_{2}$ : R$_{1}$(X), W$_{1}$(X), R$_{2}$(Y), R$_{1}$(Y), W$_{1}$(Y), W$_{2}$(Y)

these two schedules are conflict equivalent.

in other words, i can say, S$_{2}$ is conflict equivalent to S$_{1}$

 

 number of schedules which are conflict equal to S$_{1}$

if you follow the approach like in the following link, you will found answer as 4

https://gateoverflow.in/118640/gate2017-2-44?show=289691#a289691

one is the original one, i.e., S$_{1}$ and one more is S$_{2}$

remaining two are

S$_{3}$ : R$_{1}$(X), R$_{2}$(Y), W$_{1}$(X), R$_{1}$(Y), W$_{1}$(Y), W$_{2}$(Y)

S$_{4}$ : R$_{2}$(Y), R$_{1}$(X), W$_{1}$(X), R$_{2}$(Y), R$_{1}$(Y), W$_{1}$(Y), W$_{2}$(Y)

 

Note :- If  a Schedule is not conflict serializable then NONE of it's conflict equivalent schedules are conflict serializable.


number of serial schedules which are conflict equal to S$_{1}$?

Here, you are Comparing Serial schedules with given Schedule like

for(i=0;i<n;i++)

{
    if( a[i] == j)
    {
        
    }
    else
    {
        
    }
}

here i is variying but not j. So, i represent Serial Schedule and j represent given Schedule S$_{1}$

 

There are 2 Transactions, So you have 2 ! = 2  Serial schedules. And None of them is equivalent to S$_{1}$



Let T$_{1}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), W$_{1}$(Y) and  T$_{2}$ : R$_{2}$(Y), W$_{2}$(Y)

No.of Total Schedules Possible = $\frac{(4+2)!}{4!.2!} = \frac{720}{48}  = 15 $

No.of Serial Schedules Possible = 2 ! = 2

Non-Serial Schedules = (10-2)=13 Schedules, in that Some are conflict equivalent to T$_{1}$ to T$_{2}$, Some are conflict equivalent to T$_{2}$ to T$_{1}$ and some of them not equivalent to any serial schedule.

 

let S : R$_{1}$(X), W$_{1}$(X), R$_{2}$(Y), W$_{2}$(Y),  R$_{1}$(Y), W$_{1}$(Y)

 

 number of schedules which are conflict equal to S

Answer : 6 including S

number of serial schedules which are conflict equal to S?

Answer is 1. ( T$_{2}$ to T$_{1}$ )

 

The total number of conflict serializable schedules that can be formed by T1 and T2 is

No.of conflict serializable schedules = No.of conflict equivalent to Schedule T$_{1}$ to T$_{2}$ + No.of conflict equivalent to Schedule T$_{2}$ to T$_{1}$  = 1 + 6 = 7

Non-Conflict serializable schedules = 15-7 = 8

 

Those 8 schedules are :

S$_{1}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), R$_{2}$(Y), W$_{1}$(Y), W$_{2}$(Y)

and it's remaining 3 conflict equivalent schedules.

 

S$_{5}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), R$_{2}$(Y), W$_{2}$(Y), W$_{1}$(Y)

and it's remaining 3 conflict equivalent schedules.

by (539 points)
0

number of schedules which are conflict equal to S

Answer : 6 including S

 

number of serial schedules which are conflict equal to S?

Answer is 1. (T2 to T1 )

Sir,dint understand this part. For T1 to T2 it should be 1 right? Also, i dint understand the last part how you found those 8 schedules.

0
Can't you apply the method which provided on gate question, to found how it is 6 ?


Which serial schedule is conflict equivalent to given schedule ? T2 -> T1 but not T1 -> T2.


Finding Those eight schedules need some experience, i just want to show the sum is obtained to no.of schedules
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jan 2020
  1. shashin

    1163 Points

  2. Vimal Patel

    306 Points

  3. Deepakk Poonia (Dee)

    305 Points

  4. Debapaul

    237 Points

  5. Satbir

    192 Points

  6. SuvasishDutta

    137 Points

  7. Pratyush Priyam Kuan

    118 Points

  8. tp21

    108 Points

  9. DukeThunders

    95 Points

  10. pranay562

    95 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
2,988 questions
1,509 answers
8,935 comments
89,814 users