self doubt(conflict serializable)

Question

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??.

Comments

https://gateoverflow.in/118640/gate2017-2-44

---

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.

---

@shaikh thnxx ver much for uploading these images

thesereally helped me

Answer 1

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)

Comments

Can u give some good reference?

I was getting some doubt

---

Mam, I don't have any reference

---

So, from where u got the idea?

---

By practicing more problems (seeing different approaches by different people in different questions  in GO ), I get this procedure.

---

In question 1). why u not considering W(B)

but why it has no conflict with R(A) and W(A)

right?

---

in that case1 means, w2(B) come before r1(A) and w1(A)

case 2 means, w2(B) comes after r1(A) and before w2(A)

case 3 means, w2(B) comes after r1(A) and w1(A).

---

@Shaik

Here view equivalent schedule not possible

rt?

---

they didn't mentioned any schedule, therefore the view equivalent question is invalid

but we can find all the view equivalent schedules to T1 --> T2

or T2 --> T1

---

@shaik masthan i understood the second part T2->T1(53) of first question but i am not getting T1->T2 of first question why there is only one possibility is it because in same schedule they should follow the same order but my doubt is that r(a) w(a) and r(b)w(b) is there one on data item a and other on b so cant they permute beacuse they are on reading and writing on different data item so how it will make difference in answer 

why cant they should be like these R(B)W(B)R(A)W(A)R(C)W(C)R(B)W(B)

then we can get more possiblity 

 please tell me where i am going wrong

 

---

why there is only one possibility is it because in same schedule they should follow the same order

yes, with in a transaction you have to follow the order ===> after completing the operation R(B) it should go to W(B) then R(C) after that only W(C)

---

Ok got it

:)

---

@ShaikMasthan Should we consider write-read conflicts only??

---

Yes

---

Why though?
I mean why should'nt we consider write-write or read-write as they are also conflicting actions?

---

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

---

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?

---

on each data item...

---

Yes for each data item Q..

Am i thinking it right?

---

Gr8 explanation. It took 15 mins to understand from your explanation.I am just thinking how would i solve such questions in xam.

---

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.

---

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 !

---

@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..

 

---

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 !

---

You solved the 2nd question in one method only right?

---

No, i solved 2nd question in two approaches !

infact 1st question new approach kept in some other question

---

@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 :/ "

---

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

---

Then in this case answer is not coming right

only one arrangement is possible you see

1 -->2 ---> 3--->4---->6---->7--->8--->9  :/

---

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

---

I'm talking about Question no 1 )

---

@magma

is question no.1 present in this answer ( DAG approach ) ?

---

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  ?

---

thanks :)

---

@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?