Timestamp Ordering Protocol in DBMS

 Concurrency Control techniques in DBMS

Multiple transactions executing at the same time on the same data, it may affect the result of the transaction. 

In order to maintain the concurrent access of transactions, different protocols are introduced.

• Lock Based Protocol

• Time-Stamp Based Protocol

• Validation Based Protocol 

Timestamp Ordering Protocol

• The Timestamp Ordering Protocol is used to order the transactions based on their Timestamps.
• The order of the transaction is ascending order of the transaction creation.
• This is the most commonly used concurrency protocol.
• Lock-based protocols help you to manage the order between the conflicting transactions when they will execute.
• Timestamp-based protocols manage conflicts as soon as an operation is created.
• The priority of the older transaction is higher.
• The protocol uses the System Time or Logical Count as a Timestamp..
• 
  
• Example:- 
• Two transactions T1 and T2. Suppose the transaction T1 has entered the system at 007 times and transaction T2 has entered the system at 009 times. T1 has the higher priority, so it executes first as it is entered the system first.
• The timestamp ordering protocol also maintains the timestamp of the last 'read' and 'write' operation on a data.

TS(TI) denotes the timestamp of the transaction Ti.

R_TS(X) denotes the Read time-stamp of data-item X.

W_TS(X) denotes the Write time-stamp of data-item X.

 

Following are the Timestamp Ordering Algorithms

 

1. Basic Timestamp Ordering

·        It compares the timestamp of T with Read_TS(X) and Write_TS(X) to ensure that the transaction execution is not violated.

·        If the transaction execution order is violated, transaction T is aborted and resubmitted to the system as a new transaction with a new timestamp.

 

2. Strict Timestamp Ordering

·        It ensures that the schedules are both strict for easy recoverability and conflict serializability.

 

3. Thomas's Write Rule
It provides serializability order does not enforce conflict serializability.

It improves the Basic Timestamp Ordering Algorithm and ignores outdated writes.

It rejects some write operations, by modifying the checks for the write_item(X) operation as follows,

The basic Thomas write rules are as follows:

1. If Read_TS(X) > TS(T) (read timestamp is greater than timestamp transaction), then abort and rollback transaction T and reject the operation.

2. If Write_TS(X) > TS(T) (write timestamp is greater than timestamp transaction), then do not execute the write operation but continue processing. Because some transaction with a timestamp is greater than TS(T) and after T in the timestamp has already written the value of X.

3. If neither the condition transaction 1 nor the condition in transaction 2 occurs, then execute the Write_item(X) operation of transaction T and set Write_TS(X) to TS(T).

 

If we use the Thomas write rule then some of the serializable schedules can be permitted that does not conflict with serializable:

In the above figure, T1's read and precedes T1's write of the same data item. This schedule does not conflict serializable.

Thomas write rule checks that T2's write is never seen by any transaction.

If we delete the write operation in transaction T2, then conflict with the serializable schedule can be obtained.

Outdated Write Example – 
Thomas Write Rule is ignoring the Obsolete Write Operations because some transaction with a timestamp greater than TS(T) (i.e., a transaction after T in TS ordering) has already written the value of X.

So, logically user can ignore the Write(X) operation of T which becomes obsolete.

Suppose a user has a schedule in which two transactions T₁ and T₂. Now, TS(T₂) < TS(T₁). This means T₁ arrived after T₂ and hence has a larger TS value than T₂.

This implies that the serializability of the schedule allowed is T₂ –> T₁. Consider the partial schedule given below: 

Obsolete Writes are hence ignored in this rule which is in accordance with the 2^nd protocol.

It seems to be more logical as users skip an unnecessary procedure of restarting the entire transaction.

This protocol is just a modification to the Basic TO protocol.

 

Basic TO Protocol v/s Thomas Write Rule – 
Suppose in a schedule two transactions T₁ and T₂. Now, TS(T₂) < TS(T₁).

This implies that serializability of schedule allowed is T₂ –> T₁ .

R_i(A) implies Read and W_i(A) implies Write operation. Now, the types of partial schedules allowed in both Basic TO and Thomas Write Rule, the difference in operations of both are:- 

 

Basic TO Protocol ·         Not Allowed  R1(X) W2(X) W1(X) R2(X) W1(X) W2(X) ·         Allowed  All operations where T2 occurs before T1. R1(X) R2(X)	Thomas Write Rule ·         Not Allowed  R1(X) W2(X) W1(X) R2(X) ·         Allowed  All operations where T2 occurs before T1. Outdated Writes: W1(X) W2(X) R1(X) R2(X)

=============================================

Advantages and Disadvantages of TO protocol:

• TO the protocol ensures serializability since the precedence graph is as follows:

• Schedules are serializable (such that the equivalent serial schedule is arranged in order of the age of the participating transactions.)

  • No waiting for the transaction, which eliminates the possibility of deadlocks!
  • But the schedule may not be recoverable and may not even be cascade-free.

   

  Disadvantages:

  Starvation is possible if the same transaction is restarted and continually aborted

   

  =====================================================