6

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.

4
+200

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.

  • In my question I have written that serializable order is R1(X), W1(X). That should be R1(X), W2(X). And if I consider this one than it's easy to see that it is view equivalent to serial schedule T1, T2. So that was my silly mistake. – Vimal Patel Nov 21 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.