Thomas Write Rule & Timestamp based Concurrency Control | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Thomas Write Rule in DBMS

Timestamp Ordering Protocol states that if Ri(X) and Wj(X) are conflicting operations then R_i (X) is processed before W_j(X) if and only if TS(T_i) < TS(T_j). Whenever a schedule does not follow serializablity order according to the Timestamp, user generally reject it and rollback the Transaction. Some operations on the other hand are harmless and can be allowed.
Thomas Write Rule allows such operations and is a modification on the Basic Timestamp Ordering protocol. In Thomas Write Rule user ignore outdated writes. Moreover, of all the Concurrency Protocols have been discussed, Concurrency is imposed on Schedules which are Conflict Serializable, in Thomas Write Rule, the most important improvement is user can achieve Concurrency with View Serializable schedules.
First let’s state what is Thomas Write Rule and then what are the modifications and improvements it succeeds over the Basic TO protocol.

1. Thomas Write Rule
Thomas Write Rule does not enforce Conflict Serializablity but rejects fewer Write Operations by modifying the check Operations for W_item(X)

• If R_TS(X) > TS(T), then abort and rollback T and reject the operation.
• If W_TS(X) > TS(T), then don’t execute the Write Operation and continue processing. This is a case of Outdated or Obsolete Writes. Remember, outdated writes are ignored in Thomas Write Rule but a Transaction following Basic TO protocol will abort such a Transaction.
• If neither the condition in 1 or 2 occurs, then and only then execute the W_item(X) operation of T and set W_TS(X) to TS(T)

2. Outdated Write Example
The main update in Thomas Write Rule is ignoring the Obsolete Write Operations. This is done because some transaction with timestamp greater than TS(T) (i.e., a transaction after T in TS ordering) has already written the value of X. Hence, logically user can ignore the Write(X) operation of T which becomes obsolete. Let us see this through an example:
Suppose 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 serializablity of schedule allowed is T₂ → T₁ . Consider the partial schedule given below:

Example of Outdated Write 

Obsolete Writes are hence ignored in this rule which is in accordance to the 2nd protocol. It seems to be more logical as user skip an unnecessary procedure of restarting the entire transaction. This protocol is just a modification to Basic TO protocol.

3. Basic TO Protocol v/s Thomas Write Rule
Suppose user has a schedule in which two transactions T₁ and T₂. Now, TS(T2) < TS(T1). This implies that serializablity of schedule allowed is T2 → T1 . Consider the two protocols, let us see what types of Operation will be allowed and not allowed under them. Ri(A) implies Read and Wi(A) implies Write operation. Now, let us look at the types of partial schedules allowed in both Basic TO and Thomas Write Rule, you’ll understand the difference in operations of both the protocol. User distinguish in operations Allowed and Not Allowed in both of the Protocols.

Thus, from the above gist, this modification used in Thomas Write Rule in comparison to Basic TO protocol.

Timestamp based Concurrency Control

Concurrency Control can be implemented in different ways. One way to implement it is by using Locks. Now, lets discuss about Time Stamp Ordering Protocol.
As earlier introduced, Timestamp is a unique identifier created by the DBMS to identify a transaction. They are usually assigned in the order in which they are submitted to the system. Refer to the timestamp of a transaction T as TS(T).

1. Timestamp Ordering Protocol
The main idea for this protocol is to order the transactions based on their Timestamps. A schedule in which the transactions participate is then serializable and the only equivalent serial schedule permitted has the transactions in the order of their Timestamp Values. Stating simply, the schedule is equivalent to the particular Serial Order corresponding to the order of the Transaction timestamps. Algorithm must ensure that, for each items accessed by Conflicting Operations in the schedule, the order in which the item is accessed does not violate the ordering. To ensure this, use two Timestamp Values relating to each database item X.

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

2. Basic Timestamp Ordering
Every transaction is issued a timestamp based on when it enters the system. Suppose, if an old transaction T_i has timestamp TS(T_i), a new transaction T_j is assigned timestamp TS(T_j) such that TS(T_i) < TS(T_j). The protocol manages concurrent execution such that the timestamps determine the serializability order. The timestamp ordering protocol ensures that any conflicting read and write operations are executed in timestamp order. Whenever some Transaction T tries to issue a R_item(X) or a W_item(X), the Basic TO algorithm compares the timestamp of T with R_TS(X) & W_TS(X) to ensure that the Timestamp order is not violated. This describe the Basic TO protocol in following two cases.

• Whenever a Transaction T issues a W_item(X) operation, check the following conditions:
  (i) If R_TS(X) > TS(T) or if W_TS(X) > TS(T), then abort and rollback T and reject the operation. else,
  (ii) Execute W_item(X) operation of T and set W_TS(X) to TS(T).
• Whenever a Transaction T issues a R_item(X) operation, check the following conditions:
  (i) If W_TS(X) > TS(T), then abort and reject T and reject the operation, else
  (ii) If 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 the Basic TO algorithm detects two conflicting operation that occur in incorrect order, it rejects the later of the two operation by aborting the Transaction that issued it. Schedules produced by Basic TO are guaranteed to be conflict serializable. Already discussed that using Timestamp, can ensure that our schedule will be deadlock free.
One drawback of Basic TO protocol is that it Cascading Rollback is still possible. Suppose we have a Transaction T₁ and T₂ has used a value written by T₁. If T₁ is aborted and resubmitted to the system then, T must also be aborted and rolled back. So the problem of Cascading aborts still prevails.
Let’s gist the Advantages and Disadvantages of Basic TO protocol:

• Timestamp Ordering protocol ensures serializablity since the precedence graph will be of the form:
  Precedence Graph for TS ordering
• Timestamp protocol ensures freedom from deadlock as no transaction ever waits.
• But the schedule may not be cascade free, and may not even be recoverable.

3. Strict Timestamp Ordering
A variation of Basic TO is called Strict TO ensures that the schedules are both Strict and Conflict Serializable. In this variation, a Transaction T that issues a R_item(X) or W_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.