Page 164 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Unit 9: Transaction Management

To implement this concurrency control scheme, every database object O is given a read timestamp Notes
RTS(O) and a write timestamp WTS(O). If transaction T wants to read object O, and
TS(T) < WTS(O), the order of this read with respect to the most recent write on O would violate
the timestamp order between this transaction and the writer. Therefore, T is aborted and restarted
with a new, larger timestamp. If TS(T) > WTS(O), T reads O, and RTS(O) is set to the larger of RTS(O)
and TS(T).

Notes There is a physical change the change to RTS(O) to be written to disk and to be
recorded in the log for recovery purposes, even on reads. This write operation is a significant
overhead.
Observe that if T is restarted with the same timestamp, it is guaranteed to be aborted again, due
to the same conflict. Contrast this behavior with the use of timestamps in 2PL for deadlock
prevention: there, transactions were restarted with the same timestamp as before in order to
avoid repeated restarts. This shows that the two uses of timestamps are quite different and
should not be confused.

Next, let us consider what happens when transaction T wants to write object O:
1. If TS(T) < RTS(O), the write action conflicts with the most recent read action of O, and T is
therefore aborted and restarted.

2. If TS(T) < WTS(O), a naive approach would be to abort T because its write action conflicts
with the most recent write of O and is out of timestamp order. It turns out that we can
safely ignore such writes and continue. Ignoring outdated writes is called the Thomas
Write Rule.
3. Otherwise, T writes O and WTS(O) is set to TS(T).

The Thomas Write Rule

We now consider the justification for the Thomas Write Rule. If TS(T) < WTS(O), the current
write action has, in effect, been made obsolete by the most recent write of O, which follows the
current write according to the timestamp ordering on transactions. We can think of T’s write
action as if it had occurred immediately before the most recent write of O and was never read by
anyone.

If the Thomas Write Rule is not used, that is, T is aborted in case (2) above, the timestamp
protocol, like 2PL, allows only conflict serializable schedules. (Both 2PL and this timestamp
protocol allow schedules that the other does not.) If the Thomas Write Rule is used, some
serializable schedules are permitted that are not conflict serializable, as illustrated by the schedule
in table below. Because T ’s write follows.
2
A Serializable Schedule that is not Conflict Serializable

T1 T2
R(A)
W(A)
Commit
W(A)
Commit

LOVELY PROFESSIONAL UNIVERSITY 157