Intro to DBMS

Timestamp Ordering Protocol

The Timestamp Ordering Protocol arranges the transactions based on their respective timestamps. A timestamp is a numeric value assigned to a transaction when it arrives in a schedule. Usually, this timestamp value is assigned in ascending order.

Example: Suppose three transactions, T1, T2, and T3, execute in parallel on the same data A.

  • “T1 arrived at 8:00 AM. Please assign a timestamp value of 100 and call it ‘Older.’
  • “T2 arrived at 8:10 AM, so please assign a timestamp value of 200 and name it ‘Younger.’
  • “T3 arrived at 8:15 AM. Therefore, assign a timestamp value of 300 and name it ‘Youngest.’

Always execute the transaction that comes first or has the minimum timestamp value.

The following is the notation of the timestamp.

TS (Ti)

Where TS is the timestamp, and Ti is the transaction number.

Note: In some cases, timestamp values may be given in descending order. The youngest transaction in a schedule may hold the lowest timestamp value.

Timestamp Types

The timestamp of any data is  of two types

  1. Read timestamp (RTS)
  2. Write timestamp (WTS)

1. Read the Timestamp of the Data

The Read timestamp refers to the timestamp of the last successful read operation on data A.

It is denoted by RTS (“data”) = timestamp-Value.

Example:

Timestamp Ordering Protocol: Read Data

According to the above diagram, data “A” was last read by transaction T3. Therefore, the read timestamp for data “A” will be the same as that of the least recent transaction.

RTS (“A”) = 300

2. Write Timestamp of Data

The Write timestamp is the timestamp of the latest successful write operation on the same data.

 It is denoted by WTS (Ti) = timestamp-Value.

Example:

Timestamp Ordering Protocol: Write Data

As shown in the diagram, T2 is the most recent transaction that wrote data “A,” thus establishing the write timestamp of the data, which is given below.

WTS (A) = 200

If multiple data items are in the schedule (i.e., A, B, C…), each data item holds its own Read and Write timestamp as given below.

Timestamp Ordering Protocol: Write Data

  • RTS(A) = 300
  • WTS(A) =200
  • RTS(B) =100
  • WTS(B) =100

Timestamp Ordering Protocol Rules

Timestamps follow some rules to perform read or write operations. The rules are also known as Thomas rules.

Rule No. 01 is utilized when a transaction requires a Read (A) operation.

  • If WTS(A) > TS (Ti), then Ti Rollback
  • Else (otherwise) execute R(A) operation and SET RTS (A) = MAX {RTS(A), TS(Ti)}

Rules No.2 rules are used when a transaction needs to perform WRITE (A)

  • If RTS(A) > TS (Ti), then Ti Rollback.
  • If WTS(A) > TS (Ti), then Ti Rollback.
  • Else (otherwise) execute the W(A) operation and SET WTS (A) = TS(Ti).

Where “A” is some data

Advantages of Timestamp Protocol

The Timestamp protocol ensures serializability and Deadlock removal because a transaction with a smaller timestamp (TS) executes before a transaction with a higher TS.

  • If T1 timestamp = 100
  • T2 timestamp = 200
  • T3 timestamp = 300

Following is the sequence of transaction execution.

Disadvantages of Timestamp Protocol

  • The schedule may not be recoverable.
  • The schedule may not be cascading-free.