Timestamp Based Protocol 1

Timestamps

With each transaction Ti in the system, we associate a unique fixed timestamp, denoted by TS (Ti ). This timestamp is assigned by the database system before the Transaction Ti starts execution.

If a transaction Ti has been assigned timestamp TS(Ti) and a new transaction Tj enters the system, then TS(Ti )W-timestamp (Q): denotes the largest timestamp of any transaction that executed write(Q) successfully.

2. R-timestamp (Q): denotes the largest timestamp of any transaction that executed read(Q) successfully.

The timestamp ordering protocol

1. Suppose that transaction Ti issues read (Q)

• If TS(Ti) < W-timestamp(Q), then Ti needs to read value of Q that was already overwritten. Hence read operation is rejected and Ti is rolled back.
• if TS(Ti) < W –timestamp(Q), the read operation is executed and R-timestamp(Q) is set to the maximum of R-timestamp(Q) and TS(Ti)

2. Suppose that transaction Ti issues write(Q)

• If TS(Ti) < R- timestamp(Q), then the value of Q that Ti­ is producing was needed previously and the system assumed that, that value would never be produced, Hence the system rejects the write operation and rolls Ti ­back.
• If TS(Ti)
• Otherwise, the system executes the write operation and sets W-timestamp to TS(Ti)

Few Points

1. Timestamp Ordering protocol ensures conflict serializability.
2. The protocol ensures freedom from the deadlock, since no transaction ever waits. However, there is a possibility of Starvation of long transaction if a sequence of conflicting start transactions caused repeated restarting of the long transaction.
3. Protocol generates the schedules that are not recoverable.

Thomas Write Rule (modification to Timestamp ordering protocol)
Ensures greater potential concurrency
Suppose that Transaction Ti issues write(Q)

• If TS(Ti) < R- timestamp(Q), then the value of Q that Ti­ is producing was needed previously and the system assumed that, that value would never be produced, Hence the system rejects the write operation and rolls Ti ­back.
• If TS(Ti)
• Otherwise, the system executes the write operation and sets W-timestamp to TS(Ti).