search
Log In
8 votes
1.9k views
Q.1 find total number of conflict serializable

T1=R(A)W(A)R(B)W(B)

T2=R(B)W(B)R(C)W(C)

Q.2 find total number of conflict serializable for

T1=R1(A)W1(A)R1(B)W1(B)R1(C)W1(C)

T2=R2(A)W2(A)R2(B)W2(B)R2(C)W2(C).

explanation??.
in Databases 1.9k views
0
Q1 ) 54  ??
0
yes ,explanation??
0

Actually, the answer provided in GATE-2017 question, didn't satisfy me.

I did with my approach, you may check it.

@BASANT KUMAR

Don't add two different questions, in one post from next time.

1
@shaikh thnxx ver much for uploading these images

thesereally helped me

1 Answer

15 votes
 
Best answer

NEW APPROACH :-

For question 1 :-

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

For question 2:-

Before coming to question 2, please understand the procedure which is used in the Q1, due to it is same concept

For clarity images :- https://drive.google.com/open?id=1dka-cqVm6ZppPI81Mm9WztqV_pG5iMMh

Recommended to see the same type of question  https://gateoverflow.in/272638/total-conflict-serializable-schedules

 

OLD APPROACH :-

For Question 1 :-

For clarity images https://drive.google.com/open?id=1o12YFKd8JLhlXWLB1D3tuph91ENJ0OCd



For Question 2 :-

For Case 3 and Case 4 :-

Note that R2(B) should be after W1(B)


selected by
0
those are already taken care by w-r conflict itself.

if in the question, it have only read in T1 and write in T2, then consider read-write conflict
1
So while finding schedules conflict equivalent to T1 → T2, for any data item Q, we need to find the first action on Q by T2  that conflicts with any of the action on Q by T1 and that would cover up all the remaining conflict.

Am I getting it right?
0
on each data item...
0
Yes for each data item Q..

Am i thinking it right?
0
Gr8 explanation. It took 15 mins to understand from your explanation.I am just thinking how would i solve such questions in xam.
1
if you understood the method, and practice enough, with in 5 min you can do it !

By the way, 2$^{nd}$ question can't give in GATE, they give only small problem which can we do with in 5 min.
0
i added one more approach to solve this type of questions with in less time with some more preciously.

i recommended You to check it !
0

@Shaik Masthan

Can you please explain the solution to the 2nd question a bit?

I am not getting the cases..The way I solved is giving me more no. of schedules..

 

0
new approach or old approach ?

if you doesn't get old approach is, there is no problem

new approach is very easy and less time consume and no need to bother about intersection cases !
0
You solved the 2nd question in one method only right?
0
No, i solved 2nd question in two approaches !

infact 1st question new approach kept in some other question
0

@Shaik Masthan

why you only take Write - Read conflict  here

By draw topological diag it's very easy to solve but I didn't understand that how you made it

acc to question 2

This topology is correct ???

but acc to this topology "correct answer is not coming :/ "

0

why you only take Write - Read conflict  here

that is DAG, So excess links removed !

if you didn't get it, just assume, 3 --> 6 you drawn a link.

Then think 6 should be after 3 and 4, and 4 should be after 3 ==> you must have to do 3--> 4--->6

Your DAG, representating T1 --> T2

0
Then in this case answer is not coming right

only one arrangement is possible you see

1 -->2 ---> 3--->4---->6---->7--->8--->9  :/
0
you calculated upto T1 --> T2 part

Now calculate T2 --> T1 part

then add both of them

for DAG approach, Question1 kept on another link, ( which is at GATE question )

Question 2 is only present here
0
I'm talking about Question no 1 )
0
@magma

is question no.1 present in this answer ( DAG approach ) ?
0
No it's not present

But we can use this DAG approach in  similar type of questions where we have to find no of conflict serializable right  ?
0
thanks :)
0

@Shaik Masthan

In the first method, second image –

 https://drive.google.com/file/d/1Z-tlThOEyVlBjV8Zky5_Wc3z7L-hvSGc/view?usp=sharing

Total number of possibilities such that T2->T1 = T1->T2 = 56 is because of the symmetricity of the DAG, right? i.e if we draw the graph for T2->T1 it will be same as that of T1->T2 with the corresponding labels interchanged(G for A, H for B etc) , right?

Related questions

1 vote
0 answers
1
134 views
My question, does abort in T2 makes this schedule conflict serializable? as the effect of T2 will be null. T1: Rx T2: Wx T1: Wx T2: ABORT T1: COMMIT Rx – read item x. Wx – write item x.
asked Dec 31, 2018 in Databases susgir2 134 views
2 votes
1 answer
2
88 views
If some schedule is not conflict serializable then it can never be view serializable is it true? Or vice versa.
asked Jan 26, 2018 in Databases ankit_thawal 88 views
0 votes
1 answer
3
283 views
Account on the following statements IF Conflict Serial schedule then it is ALWAYS possible under 2PL
asked Sep 18, 2016 in Databases pC 283 views
0 votes
0 answers
4
...