How to solve this question.

Question

A schedule S contains three transactions $T_1$, $T_2$, $T_3$ and the oeprations sequence is given below:

$T_1$: $Read$ $A$; $T_2$: $Write$ $A$; $T_3$: $Read$ $A$; $T_1$: $Write$ $A$; $T_3$: $Write$ $A$ and all the above transactions are committed.

Is the above schedule is serializable or not? If yes it is equivalent to which serial schedule. Find the proper combination of the given alternatives from I to VII

Comments

it is view serializable. Serial schedule  is 1->2->3

---

Please explain the answer.

---

It is clearly not conflict serializable as the graph has a cycle

checking for view serializability:-

1. final write is of t3 and t1 ,t2 also write on the variable a so t1 and t2 must come before t3.

2. initial read on variable a is from t1 and t2,t3 write on a so t1 must come before t2 ,t3

3. updated read is from t2 to t3. as t1 writes a so t1 cannot come between t2 and t3.

     so the serial schedule that satisfies the above 3 points is t1->t2->t3.

Answer 1

To check serializability we perform following steps:-

1) Checking for conflict pairs(Read-Read,Read-Write,Write -Write)

2) Make precedence graph where all the transactions are the vertices and to check whether there exists directed edges in between them we check for the conflict pairs

3) If no cycles are found the schedule is conflict serializable and by drawing the topological sequence we get the serial order

4) If cycle or loop present then we check for blind writes

5) If blind write is not present (and schedule not conflict serializable ),then the schedule is not serializable

6) If blind write is present and schedule is not conflict serializable then we check for view serializability

7) To check for view serializable schedule we-

   a) check for initial read, updated read(or can say WR conflict) and final write orders and try to match with all the serial schedules possible ( factorial of total transactions involved in the schedule which is here 3!=6)

   b)if match found schedule view serializable and the particular match is the serial order.

  c)if not then schedule is not serializable.

 

now in the above problem clearly loop exists between T1 and T2 as we get edge from T1 to T2 due to R1(A),W2(A) and we get another edge from T2 to T1 due to W2(A),W1(A) so no need to check further conflict pairs for edges.

now checking for blind writes. yes blind write from T1 to T3 exists. So schedule may be view serializable.

Now the 6 possible serial schedules can be->

1->2->3

1->3->2

2->1->3

2->3->1

3->1->2

3->2->1

Now check for initial read. T1 firsts read A then T3. so only 1st two schedules are possible match.forget about the rest.

Now T3 has the final read and only WR conflict is T2 to T3. So we get the order as T2->T3, also T3 has the final read.

So final serial order is 1->2->3

Comments

very well sanchit jain’s students 😄