Awesome q2a theme
0 votes
39 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) | 39 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 (622 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 Apr 2020
  1. Kushagra गुप्ता

    36 Points

  2. !KARAN

    36 Points

  3. Ram Swaroop

    36 Points

  4. sushmitagoswami

    6 Points

  5. ConnieSincla

    5 Points

  6. MelinaCundif

    5 Points

  7. Lolita04I641

    5 Points

  8. JackiBandy49

    5 Points

  9. skbansal97

    5 Points

  10. Rijusen

    5 Points

3,522 questions
1,658 answers
10,465 comments
90,046 users