Timestamp based Ordering Protocol in DBMS

In the previous chapter, you learned lock based protocol in DBMS to maintain the integrity of database. In this chapter, you will learn Timestamp based ordering protocol.

What is Timestamp Ordering Protocol?

• Timestamp ordering protocol maintains the order of transaction based on their timestamps.
• A timestamp is a unique identifier that is being created by the DBMS when a transaction enters into the system. This timestamp can be based on the system clock or a logical counter maintained in the system.
• Timestamp helps identifying the older transactions (transactions that are waiting in line to be executed) and gives them higher priority compared to the newer transactions. This make sure that none of the transactions are pending for a longer period of time.
• This protocol also maintains the timestamps for the last read and last write on a data.
• For example, let’s say an old transaction T1 timestamp is TS(T1) and a new transaction T2 enters into the system, timestamp assigned to T2 is TS(T2). Here TS(T1) < TS(T2) so the T1 has the higher priority because its timestamp is less than timestamp of T2. T1 would be given the higher priority than T2. This is how timestamp based protocol maintains the serializability order.

How a Timestamp ordering protocol works?

Let’s see how a timestamp ordering protocol works in a DBMS system. Let’s say there is data item A in the database.

W­_TS(A) is the largest timestamp of a transaction that executed the operation write(A) successfully.
R_TS(A) is the largest timestamp of a transaction that executed the operation read(A) successfully.

1. Whenever a Transaction Tn issues a Write(A) operation, this protocol checks the following conditions:
   • If R_TS(A) > TS(Tn) or if W_TS(A) > TS(Tn), then abort and rollback the transaction Tn and reject the write (A) operation.
   • If R_TS(A) <= TS(Tn) or if W_TS(A) <= TS(Tn) then execute Write(A) operation of Tn and set W_TS(A) to TS(Tn).
2. Whenever a Transaction Tn issues a Read(A) operation, this protocol checks the following conditions:
   • If W_TS(A) > TS(Tn), then abort and reject Tn and reject the Read(A) operation.
   • If W_TS(A) <= TS(Tn), then execute the Read(A) operation of Tn and update the timestamp R_TS(A).

Advantages of Timestamp based protocol

• Schedules managed using timestamp based protocol are serializable just like the two phase protocols
• Since older transactions are given priority which means no transaction has to wait for longer period of time that makes this protocol free from deadlock.