View serializability


#1

d2


#2

Really difficult question. But i would try to explain it in a easy way.

The given schedule is:

T1     T2     T3     T4     T5     
r(A)      
              r(B)
w(B)
       r(B)
                     r(B)
       w(C)
                            r(C)

                     w(E)
                            r(E)
                            w(B)

Read the table from top to bottom. The 1st row executes first then the 2nd row and so on till the last row.

Now you need to note down which Transaction is reading the initial value of the variables before any write operation.

Variable A : Read by T1 before any write operation on A.
Variable B: No transaction reads the initial value of B. (Note T2 reads B only after T1 writes on it)
Variable C: No transaction reads the initial value of C.
Variable D: Read by T3 before any write operation on D.
Variable E: No transaction reads the initial value of C. ------------> Constraint(1)

Just keep the above 5 lines aside for now. We would be dealing with them in the end.

Now let’s keep a note on the final write operation.

Variable A : No final write operation on A.
Variable B: Final write by T5.
Variable C: No final write operation on C.
Variable D: No final write operation on D.
Variable E No final write operation on A. ------------------> Constraint(2)

Just keep the above 5 lines aside for now. We would be dealing with them in the end.

Now the main part comes into picture. We would be preserving the write-read dependency if any.
If you closely observe the table then there are 4 write-read dependencies:

  1. T1->T2 (On variable B)
  2. T1->T4 (On variable B)
  3. T2->T5 (On variable C)
  4. T4->T5 (On variable E) -------------> Constraint(3)

The above 4 dependencies means in our serial schedules that we would be generating, T1 should always be followed by T2 and T4. T2 should always be followed by T5. T4 should always be followed by T5.

Now we would be 1st constructing our serial schedules based on Constraint(3) then we would be
verifying with Constraint(2) and (1).

The possible serial schedule based on constrant(3) are:

  1. T1 T2 T4 T5 T3

  2. T1 T2 T3 T4 T5

  3. T1 T2 T4 T3 T5

  4. T1 T4 T2 T5 T3

  5. T1 T3 T2 T4 T5

  6. T1 T4 T2 T3 T5

  7. T1 T3 T4 T2 T5

  8. T1 T4 T3 T2 T5

  9. T3 T1 T2 T4 T5

  10. T3 T1 T4 T2 T5

In this question there is no need to verify constraint(1) actually. Because on variable A and variable D just one operation is performed and there is no dependencies at all.
You can check with constraint(2), it will satisfy all the above written 10 serial schedules.

So ans is 10.


#3

For understanding how did we get all these 10 solutions, look at the 3rd constraint as mentioned by @Ruturaj. From this constraint we can derive that there can be 2 base schedule:
1–> _T1_T2_T4_T5 _
2–> _T1_T4_T2_T5 _

Now coming to T3, we have 5 places to place T3 in either of the above 2 schedules.
Place T3 at the positions marked by " _ " .


#4

T3 is independent and can come in at any place …so 5 ways … And T2 and T4 can come in any order …2C1 =2 … And T5 has to come in last …so 5*2 ways = 10 …


#5

there are 10 view serializable schedules