ME TEST SERIES

Question

HOW TO SOLVE THOSE TYPE OF QUESTION?

Comments

I AM GETTING 29 OR 30 ......

WHAT IS THE ANS

---

Deepanshu How are you getting it?

I got 12 only but not sure :(

---

@MiNiPanda

Here blind write perform by w1(B) and w2(B) , blind write means write before read. 

now, w3(B) is fixed due to the rule "last operation on some item should be same in view equivalence schedule."

so leaving w3(B) we have 5 schedule, we can arrange them in 5! = 120 way .

r1(A) w1(A)can be arranging 2! way 

r2(A) w2(A) can be arranging 2! way

so total number of view equal schedule possible (120 / 2! 2! ) = 30

in all these 30 schedules  w3(B) is last transaction , it is fixed.

---

And what about initial read? Since no one is changing A so any transaction can do R(A) and that does not matter..is it the reason for which we don't need to consider initial read?

---

@MiNiPanda YEPP FROM MY VIEW 

---

@MiNiPanda MY DOUBT IS ARE WE CONSIDERING ABOVE ONE ALSO THEN 30.

IF WE EXCLUDE ABOVE ONE 29 .

SO SHOULD BE WRITE ALL OR NOT UP ABOVE

---

ARE WE CONSIDERING ABOVE ONE

Which above one i didn't get you..

---

@MiNiPanda the one which is given in question is also view serializable na......

---

Oh okay..yes good point :p should be 29..

---

@Deepanshu the ans is 30.BUT PLEASE TELL HOW R3(A) AND R2(A) IS ARRANGED IN 2! WAYS?

HOW U GOT  30?PLEASE EXPLAIN ELABORATELY.

---

do we don't need to fix initial read....R(A) is first performed by T1....in view equivalent we have to look for 1st read and last write??

---

@Avik Chowdhury SORRY IT IS R1 AND R2

---

@minipanda why we are dividing 5! By 2! 2!

Why we are doing it ? Please explain it a bit more

---

Prince Sindhiya

r1(A) w1(B) r2(A) w2(B) r3(A) w3(B)

We are fixing the last write operation w3(B) and there are remaining 5.

Now we can arrange these 5 in 5! ways but should not forget that these 5! arrangements will contain those arrangements in which w1(B) will come before r1(A) and w2(B) will come before r2(A). So whatever be the arrangements (r1(A) has to come before w1(B)) and (r2(A) has to come before w2(B)). 5! contains these 2! [arranging b/w r1(A) and w1(B)]  and 2! [arranging b/w r1(A) and w1(B)] ways included in it. So these extra have to be divided.

That's why 5! is divided by 2!*2!.

---

Ok bro i got it and that's why I drawn that polygraph see it :)

---

Hey, can someone explain to me why we aren't taking the initial read condition here? like T1 is doing the initial read of A from the database so, in every view serializable schedule, T1 should do that only I think ?

---

s9k96

Check the Best answer or See this 

https://gateoverflow.in/238438/me-test-series?show=243274#c243274

 

Answer 1

A schedule S_i that is view equivalent to another schedule S_j must the following conditions satisfied:

1. If transaction T_i reads the initial value of a data item in a schedule S_i, then transaction T_i should read the initial value of that data item in schedule S_j.

Here since all the three transactions are reading the initial values of data item A, so in the view equivalent schedule also, all the three transactions will read the value of data item A.

2. if a transaction T_i writes the value of a data item(producer) that is read by a transaction T_j (consumer) in a schedule S_i, then transaction T_i must write the value of the data item that is read by T_j in the schedule S_j.

In this question, since there are no producer-consumer dependencies between the transactions in the schedule S, so we need not worry about this condition not being satisfied in the view equivalent schedule.

3.if a transaction T_i writes the final value of a data item in schedule S_i, then transaction T_i must also write the final value of that data item in schedule S_j.

Since here transaction T3 writes the final value of data item B in the schedule S, so in all schedules that are view equivalent to S, transaction T3 must write the final value of data item B.

Hence keep W₃(B) fixed at the end. the remaining 5 operations can be arranged in 5! ways and the since the ordering of operations within a single transaction must not change, so divide 5! by 2! for each of the two transactions T1 and T2(Note: since there is only a single operation remaining in T3 after fixing W₃(B) at the end, so we need not worry about the ordering of R₃(B) since there is only one place left for it to appear, i.e. before W₃(B))

Therefore, the number of schedules that are view equivalent to S are= 5! / (2! * 2!)=30

hence 30 view equivalent schedules are possible out of which one is already given in the question, i.e. schedule S.

Answer 2

Only one schedule is possible which is  (T1 T2 T3)

Is the answer is correct ??

inform me  kindly

Comments

@Magma read question carefully it is already serial

---

Deepanshu  please explain me how to solve these type of questions ?

I didn't understood properly

Answer 3

The polygraph for it would be this right ?

Comments

But see the previous comments..The initial Read on A does not matter as no one is modifying A so it's not compulsory for T1 to read A before anyone else. So whatever be the Read order of A, all of them will be reading the same unmodified value.

---

okay so what if t2 or t2 were modifying the value of A ?

---

Then the order of initial read would have mattered