Timestamp Based Protocols in DBMS

What are Timestamp Ordering Protocols?

Timestamp-based protocols in dbms are used to order the transaction in ascending order of their creation time. The creation time is the system time or a logical counter.

The transaction which is created first or you can say older transactions are given high priority over new transactions.

For example, if there are two transactions T1 and T2. T1 enters the system at 008 and T2 enters the system at 009 then T1 is given priority over T2.

How a Timestamp Ordering Protocol Works?

Timestamp-based protocols in dbms order the transaction according to their transaction timestamps. A schedule that is ordered in the serial order of their transaction timestamp is the only serializable schedule equivalent to the timestamp-ordered-based transaction schedule.

In order to ensure that the conflicting operation occurring in the schedule does not violate the timestamp ordering two-time stamp values relating to each database item (X) are used :

• W_TS(X) (write timestamp) is the largest timestamp of any transaction that executed write(X) successfully.
• R_TS(X) (read timestamp) is the largest timestamp of any transaction that executed read(X) successfully.

Basic Timestamp Ordering

When a transaction enters a system timestamp is created for the particular transaction. Suppose if the T1 transaction enters the system then it is assigned a timestamp TS(T1) and after T1 if the T2 transaction enters the system then T2 is assigned a timestamp TS(T2). According to the Timestamp ordering protocol TS(T1)<TS(T2) because T1 is an older transaction and T2 is a new transaction created after T1.

The timestamp of the protocol determines the serializability order of the transactions. Timestamp ordering protocol ensures that any conflicting Read or write operation must follow the timestamp ordering protocols.

Suppose any transaction T tries to perform a Read(X) or Write(X) on item X. In that case, the Basic timestamp ordering algorithm compares the timestamp of Read(X) and Write(X) with R_TS(X) and W_TS(X) and ensures that the timestamp ordering protocol is not violated.

Basic timestamp ordering protocol can be checked by the following conditions:

1. When a transaction T performs a Write_item(X) operation check the following conditions :

• If Read timestamp of data item X is greater than the Timestamp of the Transaction T i.e R_TS(X) > TS(T) or if Write Timestamp of the data item X is greater than the timestamp of the transcation i.e W_TS(X) > TS(T), then abort and rollback T and reject the operation. else,
• Execute the Write_item(X) operation of T and set W_TS(X) to TS(T).

2. When a transaction T performs a Read_item(X) operation check the following conditions :

• If Write Timestamp of data item X is greater than the timestamp of the transaction T i.e W_TS(X) > TS(T), then abort and reject T and reject the operation, else
• If Write Timestamp of data item X is less than or equal to the timestamp of the transaction T i.e W_TS(X) <= TS(T), then execute the R_item(X) operation of T and set R_TS(X) to the larger of TS(T) and current R_TS(X).

Whenever there is a conflicting operation that violates the timestamp ordering protocol then the later operation is rejected and the transaction is aborted. Schedules created by the Basic timestamp ordering protocol are conflict serializable and deadlock-free.

One of the drawbacks of the Basic timestamp ordering protocol is that cascading Rollback is possible in the timestamp ordering protocol. For Example, if transactions T1 and T2 use a value written by T1. If T1 aborts and rollback before committing the transaction then T2 must also be aborted and rolled back. So cascading problems may occur in the Basic timestamp ordering protocol.

Strict Timestamp Ordering

strict timestamp ordering is a variation of basic timestamp ordering. Strict timestamp ordering ensures that the transaction is both strict and conflicts serializable. In Strict timestamp ordering a transaction T that issues a Read_item(X) or Write_item(X) such that TS(T) > W_TS(X) has its read or write operation delayed until the Transaction T‘ that wrote the values of X has committed or aborted.

Advantages

• Timestamp-based protocols in dbms ensure serializability as the transaction is ordered on their creation timestamp. The precedence graph for the timestamp ordering protocol looks as follows:

• No deadlock occurs when timestamp ordering protocol is used as no transaction waits.
• No older transaction waits for a longer period of time so the protocol is free from deadlock.
• Timestamp based protocol in dbms ensures that there are no conflicting items in the transaction execution.

Disadvantages

• Timestamp-based protocols in dbms may not be cascade free or recoverable.
• In timestamp based protocol in dbms there is a possibility of starvation of long transactions if a sequence of conflicting short transactions causes repeated restarting of the long transaction.

Learn more

You can learn more about concurrency control in DBMS from here