Schedules

Question

$1)$ Find the number of all possible conflict-equivalent and view-equivalent schedules to the following serial schedules.

    (a) r1(A), w1(B), r2(A), w2(B), r3(A), w3(B).

Comments

as per my knowledge, it is aborted.... therefore T2 can be before T1 or after T1  ===>2 view serial schedules.

if it is commited, then T1 --> T2 is view serializable

---

Answer:- 6 ?

---

one more link https://gateoverflow.in/137024/dbms-number-of-view-equal-schedules

Answer 1

It is simple permutation.

Given :Transactions T₁ T₂ T₃ each having 2 operations R(A) W(B).

Serial schedule : T₁ $\rightarrow$T₂ $\rightarrow$T₃ 

Total number of operations= 6

Total permutations possible = 6!

But, those 2 operations of each Tx should appear in particular order. $\therefore$ divide with 2! for each Tx

Also W₁(B) W₂(B) W₃(B) should appear in this order. $\therefore$ divide with 3!

i.e 6! / (2! * 2! * 2! * 3!) = $15$

This is total number of conflict-equivalent schedules possible for T₁ $\rightarrow$T₂ $\rightarrow$T₃  

Total view equivalent schedules = $30$

Hence total number of conflict equivalent schedule is 15 and total number of view equivalent schedule is 30 .

Comments

Every conflict serializable schedule is also view serializable ,  but every view serializale schedule is not conflict serializable .

That means conflict serializable is subset of view serializable. More number of vew serial schedule is possible.

Also in this question , number of view-equivalent schedules of given schedule is asked .

There is a difference between view equal and view equal to a serial schedule.

View equal schedule = (concurrent + serial )  schedule

View view-equivalent schedules to a serial schedule = only serial schedule is consider 

If a schedule S is view-equivalent to a serial schedule, we say S is view-serializable , Clearly view equal and view serializable are different from this line .

If it is given view equal only then it can include concurrent schedules also .That is the reason we can't draw polygraph here..as in polygraph we draw it for serial schedules only .

We assume either one transaction executes before or after another in serial schedule but the operations of two can be interleaved in between in concurrent schedule.

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 .

r3(A) can be arranging 2! way 

r2(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.

so number of view equal schedule is 30 .

Answer 2

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 .

r3(A) can be arranging 2! way 

r2(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's fixed.

so number of view equal schedule is 30 .

And remember view equal is different from view equal to a serial schedule.

View equal schedule = (concurrent + serial )  schedule

View view-equivalent schedules to a serial schedule = only serial schedule to consider 

the difference is the word " serial " !!

In this question only view equal is asked . 

hope this is clear now ...

Comments

sir how r3(A) and r2(A) arranged in 2! way ...please explain sir...

---

@utpal podder

check this https://drive.google.com/open?id=1-mOSyzrP5f5lARZ-W49-8pY5jWoIoNm0

---

thank you Shaik Masthan 

---

tell me one thing

after fix W₃(B)  .. 5 places left right ?

after then why we ain't  we  use the  no of concurrent schedules formula   = (2+2+1)! / 2! 2! 1!  ???

                                                                                 

---

we can do like that also.

for better understanding, i did like that.

---

this doubt is from view equivalent schedule  :

but if use  (2+2+1)!/ 2! 2! 1! we got 15 but actual  answer is 30

---

5!/ 4 = 120/4 = 30.

---

Ooh sorry my fault :p

---

@Shaik Masthan @Magma,

why initial read is not fixed, instead of 5!, why it isnt 4! ?

---

@daksirp

initial read doesn't disturb by changing them, all three transactions are read dat item X from database only.

---

I didn't get you

Acc to rule.

If t1 reads initial value of A in schedule S, then t1 should also read initial value of A in S'

this is what i understood

---

Schedule : R₁(X), R₂(X), R₃(X)

How many view equivalent schedules? is it 3 ! or 1 ?

it should be 3 !

( did you read the images, which i provided? )

---

I read.

"The initial read didnot read further" - i don't understood this line

And for the above ex : why it is 3!, It shud be 1 from my point tho im wrong.

I'm not getting bro.

---

ok, what is that one order?

is it T1 --> T2 --> T3 .

what is initial read?

R1(X), from where it is reading?

then think R2(X), from where it is Reading?

then think R3(X), from where it is Reading?

all are reading from same place, right?

then permuting them also, they read from same place.

---

@Shaik Masthan, bro i got your point, but i didnt understand the concept well.

just tell me, whether S & S' in both the cases are View Equivalent or not ??

 

---

the image is correct,

in those two examples, s and s' are view equivalent

---

ya, thx. there was some misunderstanding on initial read, now cleared :)

---

@bikram sir we are fixing w3(b) but why not R1(a) because it has performed the first read so in other schedule also it should perform the first please tell me where I am going wrong

---

@Shaik Masthan @daksirp Case 1 is not view Equivalent, someone please verify it.

---

@akshayaK

which case 1 and why you think it is not correct... give some more clarity

---

in the image @daksirp posted.

---

in case 1 : in schedule S, T2 is doing initial read on data item A,

but in schedule S', T1 is doing initial read on data item A

---

didn't you read the previous comments ?

it is the same doubt which @daksirp already asked

---

sry, i din read. im asking acc to defination

---

@Shaik Masthan : Please see this link, check initial read, it is given they are view eq, is it right ??

---

it is wrong... in S2, R1(A) reading from W2(A)

---

yaa, understood

---

can anyone check it for me https://gateoverflow.in/156383/doubt-question-on-transaction-schedules?show=156383#q156383

Answer 3

final write in T3 it cannot change either it starts from t1 or t2

T1-.>T2->T3

T2->T1->T3

Comments

check the comment section