search
Log In
1 vote
227 views
Number of serial schedules but not conflict to schedule (S)

S: r1(A),r2(A),r3(A),r4(A),w1(B),w2(B),w3(B),w4(B)
in Databases 227 views
0
do you mean the no.of serial schedules that are conflict equivalent to the above schedule?

If thats your question then i got only 1 serial schedule : T1-T2-T3-T4
0
Please explain it..

1 Answer

0 votes
Number of serial schedules which are view equivalent to S but not conflict equivalent to schedule S

Conflict equivalent Schedule is

T1->T2->T3->T4

view equivalent Schedule are

1. first read same

2. final write same

3. w-R dependency on same on same data item

T4 should be last bcz it is final write. T1,T2,T3 can be in any order for view equivalent. Here read operation doesn't matter bcz it is on single data item

Answer is 3!-1=5
1

@kavya kamish upadhya

We need to ensure that only $W_4(B)$ comes at the end right? Rest 7 operations can be in any order (maintaining relative order within each transaction). Then we can arrange the 7 operations in 7! ways and since relative order has to be maintained i.e. $R_1(A)$ has to come before $W_1(B)$,$R_2(A)$ has to come before $W_2(B)$ and $R_3(A)$ has to come before $W_3(B)$ so we have to divide it by (2!) thrice.

So shouldn't the answer be $\frac{7!}{ 2! \times 2! \times 2!}=630$ ?

0

@kavya kamish upadhya ME has solved this way, can you explain in some more depth?

0

@MiNiPanda, but in question it is only asking for serial schedule. in that way you are also calculating non serial schedule. Right?

 

@manisha11, Please edit the question. There is nothing mentioned that you are asking for view equivalent.

0

@ShubhguptaThats right..I didn't take care about the "serial" thing..

0
Number of conflict equivalent schedule are

w1->w2->w3->w4 in which r1,r2,r3,r4 arranged as 1x3x5x7x1=105

Number of view equivalent schedule are

T1->T2->T3->T4 in which r1,r2,r3,r4 arranged as 1x3x5x7x3!=630 (3! for arranging w1->w2->w3->w4 as w4 is final write )

Then No of view equivalent which are not conflict equivalent schedule =630-105=525

 

Question need correction bcz Serial is subset of Conflict is subset of View
0

@G4TE Hunter

I understand your logic of finding conflict equivalent schedules..but what are you getting after 630-105? These are the no. of schedules which are only view equivalent and not conflict equivalent right? And what does the question ask for? 

0

@Shubhgupta the question had this description only.

Related questions

1 vote
1 answer
2
181 views
T1 LOCK-X (A) LOCK-S (B) R(A) R(B) W(A) UNLOCK (A) COMMIT UNLOCK (B) is this following CONSERVATIVE 2PL ? doubt : in conservative locking schme ..all locks are aqured before starting but locks can be released at ANY time ..so conservative need not be strict/rigorous OR is it only after commit ??
asked Jan 25, 2019 in Databases jatin khachane 1 181 views
0 votes
0 answers
3
110 views
Q50. how many statements is true unrepeatable read also know as read write conflict Strict 2PL may have read write conflict 1st one given as true now my doubt is we know that read write conflict that is https://www.revolvy.com/page/Read%E2%80%93write-conflict and we also ... watch?v=mLNfpqybSZM . how we can call unrepeatable read as read write conflict 2nd one given as false but i think it is true
asked Jan 16, 2019 in Databases Gurdeep Saini 110 views
0 votes
0 answers
4
102 views
Which of the following time stamp ordering protocol(s) allow the following schedules? $T:W_1(A)\ W_2(A)\ W_3(A)\ R_2(A)\ R_4(A)$ Time stamps: $T_1=5,T_2=10,T_3=15,T_4=20$ Thomas write rule Multiversion time stamp protocol Basic Time stamp All of these
asked Jan 13, 2019 in Databases Gupta731 102 views
...