Does timestamp protocol following thomas's write rule allow non-view-serializable schedules in some cases?

Question

I have come across the following line in a text book (Database System Concepts Textbook by Avi Silberschatz, Henry F. Korth, and S. Sudarshan $6e$) page no. 686:

Thomas’ write rule allows schedules that are not conflict serializable but are nevertheless correct. Those non-conflict-serializable schedules allowed satisfy the definition of view serializable schedules (see example box).

What I understood from the above lines is that every schedule generated by timestamp protocol following Thomas's write rule is view serializable.

Now let's take the following little schedule: $S: R_1(X), W_2(X), W_1(X)$.

This schedule $S$ is allowed under timestamp protocol which follows Thomas's write rule.

And serialization order is $R_1(X), W_1(X).$

But I was not able to prove that it is view serializable.

Actually I think that it is non-view serializable because,

1. Consider serial order as $T_1, T_2$

   Now final value of $X$ is being written by $T_2$. So not equivalent.

2. Next alternative serial order is $T_2, T_1$

   here, $R_1(X)$ will read value of $X$ written by $T_1$ not original value which was there before start of both transaction. So this too is not view-equivalent.

What is going wrong here? Please help me with this one.

Answer 1

The given schedule S is:

T1    T2
----  -----
R(X)
      W(X)
W(X)

To be view serializable W2(X) must move before R1(X) or after W1(X). However, the first would violate the "initial read" rule and the second would violate the "last write" rule.

T2 starts after T1 so has a higher timestamp. When T1 comes to write X it sees that T2's timestamp on it. By Thomas' write rule the write by T1 is void and can be removed. The given schedule then becomes

T1    T2
----  -----
R(X)
      W(X)

Now all of T2's actions occur after all of T1's - the schedule is serialized.

(You have this the other way around in your question, removing W2(X). I think that is an error.)

To show that a schedule is serializable it is only necessary to show that there is at least one equivalent schedule that is serial. It is not necessary to show that every possible serial schedule is achievable. I agree that T2,T1 is not view serializable on the original schedule because of the read/ write dependency. However, T1,T2 is serializable under the Thomas write rule.

Answer 2

I don't find it clear to ask if Thomas write rule "allows" view serializable schedules. Proper question should be,"whether the schedule "generated" by thomas write rule is view serializable or not?". This rule says to ignore T1's obsolete write(x) in the schedule S:R1(X),W2(X),W1(X). It can be ignored because no other transaction will ever read it and it will not affect the schedule in any way. The schedule S as given is not serializable(neither view nor conflict) but the resulting schedule S':R1(X),W2(X) generated by thomas write rule is view serializable in the order T1->T2(It is not guaranteed to be conflict serializable in all cases).