Timestamp Based Protocol | Database Management System

Timestamp Based Protocol | Database Management System

Timestamp Based Protocol : Each transaction Ti is issued a timestamp TS(Ti) when it enters the system.

>> If an old transaction Ti has timestamp TS(Ti), a new transaction Tjhastimestamp TS(Tj) where TS(Ti) < TSIT).

>> The timestamp can be assigned using the system clock or some logical Counter that is incremented after every timestamp is assigned.

The protocol manages concurrent execution such that the timestamps determine the serializability order. Timestamp protocols do not use locks, so deadlock cannot occur.

Timestamp-Based Protocol (2)

To ensure serializability, the protocol maintains for each data Q two timestamp values:

>> W-timestamp (Q) is the largest timestamp of any transaction that executed write(Q) successfully.

>> R-timestamp (Q) is the largest timestamp of any transaction that executed read(Q) successfully.

The timestamp Ordering protocol ensures that any conflicting read and write operations are executed in timestamp order.

Timestamp-Based Protocol (3)

Suppose a transaction Ti issues a read (Q2):

>> If TS(Ti) < W-timestamp(Q), then Ti needs to read a value of Q that was already overwritten.
Hence, the read operation is rejected, and Ti is rolled back.

>> If TS(Ti) > W-timestamp (Q), then the read operation is executed.

The R-timestamp (Q) is set to the maximum of R-timestamp(Q) and TS(Ti).

Suppose that transaction Ti issues a write(Q) :

>> If TS(T) > R-timestampo AND TS(Ti)= W-timestamp(Q), then the write operation is executed.

>> If TS(Ti) < R-timestamp(Q), then the value of Q that Ti is producing was previously read by newer transaction.

Hence, the write operation is rejected, and Ti is rolled back.

If TS(Ti).<W-timestamp (Q), then Tiis attempting to write an obsolete value of Q. This rolled back.

Timestamp Example

A partial schedule for Several data items for transactions with timestamps 1,2,3,4,5,

 

Thomas’ Write Rule

Modified version of the timestamp-ordering protocol in which obsolete write operations may be ignored under certain circumstances:

>> When Ti attempts to write data item Q, if TS(Ti) < Wtimestamp(Q), then Ti is attempting to write an obsolete value of {Q}. Hence, rather than rolling back Ti as the timestamp ordering protocol would have done, this write operation can be ignored. Otherwise protocol is unchanged.

Thomas Write Rule allows greater potential concurrency. Unlike previous protocols, it allows some view-serializable Schedules that are not conflict-serializable.