View serial schedule

Question

What is the view equivalent serial schedule for the following schedule
R2(A); R1(A); W1(C); R3(C); W1(B); R4(B); W3(A); R4(C); W2(D); R2(B); W4(A); W4(B)( Marks: -0.66 )

1.   T1 → T2 → T3 → T4.
2.   T2 → T1 → T3 → T4.
3.   T1 → T3 → T2 → T4.
4.   T4 → T2 → T3 → T1

 Can anyone plz explain how to check for view equivalent schedule in detail. I am unable to solve this one.

Comments

@Arjun Sir please explain this.

---

i am getting cycle in polygraph .. it is not view serializable

can anyone please check.

after checking initial reads  and final writes

I got this poly graph

Answer 1

 Two schedules S and S' are said to be view equivalent if the following three conditions hold:
1. The same set of transactions participates in S and S', and S and S' include the
same operations of those transactions.
2. For any operation ri(X) of Ti in S, if the value of X read by the operation has
been written by an operation wj(X) of Tj (or if it is the original value of X
before the schedule started), the same condition must hold for the value of X
read by operation ri(X) of Ti in S'.
3. If the operation wk(Y) of Tk is the last operation to write item Y in S, then
w
k(Y) of Tk must also be the last operation to write item Y in S'.
 

Point 1 is very obvious.

Point 2 - simply says that reads should be similar

i.e. if in a Schedule S a Trans Ti reads a Data item 'A' which is updated by Trans Tj then in  S' also Trans Ti must read data item 'A' modified by Tj only.Also initial reads should be same i.e. If Trans Ti reads 'A' from initial database in Schedule S then in S' also Ti should read 'A' from initial database only.

Point 3 - Final write should be same.If Ti updates 'A' finally(last updation) in S then in S' also 'A' must be finally updated by same Ti only

Now for the given question

Final Writes

A  is written by T3,T4(final write).So in any View equal schedule T4  W(A) must be after T3 W(A).For View equal serial schedule we can say T4 must be executed after T3 ( denoted by T3->T4)

B is written by T1,T4.B is finally written by T4. So T1->T4 

C and D are written by only one transactions so they can't cause final updation violation.

Now checking for Reads

T3 reads C which was updated by T1 so T1->T3

T2 reads B which was updated by T1 so T1->T2

T1->T4,T1->T3,T1->T2.So we can say T1 should be the First Trans 

T4->T2 is not possible as in that case read R(B) of T2 will be from updation of Write of T4( instead of T1)

so T2->T4

with T3->T4 T1->4 and T2->T4 it is clear that T4 must be last trans

to check for T2 and T3 see that T3->T2 is not possible as T2 reads A from initial database.

so T2->T3 

Final Answer T1->T2->T3->T4

Comments

Thanks a lot for this much effort.

---

I get it now.

---

how can T1 be the first schedule in serial schedule if you add dummy transaction T0 and Tf

then write read conflict will get violated [ $0\rightarrow 2$ according  to given schedule and as per your serial schedule $0\rightarrow $ ]  

correct me if I m wrong

Answer 2

$\textbf T1$	$\textbf T2$	$\textbf T3$	$\textbf T4$
	$R(A)$
$R(A)$
$W(C)$
		$R(C)$
$W(B)$
			$R(B)$
		$W(A)$
			$R(C)$
	$W(D)$
	$R(B)$
			$W(A)$
			$W(B)$

$According\space to\space Necessary\space condition\space for\space View\space Serializablity\space :$

$\textbf{1$\longrightarrow$Initial Read}$

 

$\textbf{2$\longrightarrow$Last Write}$

$\textbf{3$\longrightarrow$Lets Merge}$

$So\space Graph\space is\space Acyclic\space Hence\space Schedule\space is\space View\space Serializable$

$So\space according\space to\space topological\space ordering\space : $

$T1\longrightarrow T2\longrightarrow T3\longrightarrow T4$

$Hence\space Option\space 1$

$Correct\space me\space if\space anything\space wrong\space$