Timestamp Protocol – Does Thomas’s Write Rule Allow Non-View-Serializable Schedules?

concurrencyprotocolserializationtimestamp

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.

Best Answer

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.

Related Question