Timestamp Ordering With Examples

Timestamp Ordering with examples is a key concurrency control technique in DBMS that ensures transactions execute in a correct time-based order without conflicts. It helps students easily understand how read and write rules work using practical step-by-step examples.

What is Timestamp Ordering in DBMS?

Timestamp Ordering is a method where each transaction is assigned a unique timestamp, and all operations must follow this order. This guarantees serializability and prevents conflicts in multi-user environments. The list of core concepts of timestamp ordering is given below.

1. Transaction Timestamp

Each transaction gets a timestamp when it starts, which determines its priority in execution.

• Definition: Unique numeric value assigned to a transaction
• Purpose: Maintains execution order
• Example: If TS(T1)=100 and TS(T2)=200, then T1 executes before T2

2. Read Timestamp (RTS)

This indicates the latest time a data item has been read.

• Definition: Highest timestamp of transactions that read a data item
• Purpose: Prevents invalid writes
• Example: If RTS(A)=200, older transactions cannot overwrite it

3. Write Timestamp (WTS)

This represents the latest time a data item was written.

• Definition: Highest timestamp of transactions that wrote a data item
• Purpose: Maintains correct write sequence
• Example: If WTS(A)=300, older transactions cannot write A

Rules of Timestamp Ordering Protocol

Timestamp Ordering follows two important rules to control read and write operations. These rules ensure consistency and avoid conflicts. The list of rules is given below.

1. Rule No. 01: Read Operation

This rule is applied when a transaction wants to perform a Read(A) operation.

• If WTS(A) > TS(Ti) → Rollback Ti
• Else → Execute Read(A) and update
  • RTS(A) = MAX {RTS(A), TS(Ti)}

2. Rule No. 02: Write Operation

This rule is applied when a transaction wants to perform Write(A).

• If RTS(A) > TS(Ti) → Rollback Ti
• If WTS(A) > TS(Ti) → Rollback Ti
• Else → Execute Write(A) and update
  • WTS(A) = TS(Ti)

Working of Timestamp Ordering Protocol

Timestamp ordering protocol checks timestamps before allowing any operation to maintain serial order. It ensures that no older transaction violates the execution order. The list of working steps is given below.

1. Checking Read Permission

• Compares TS(T) with WTS(X)
• Allows or rejects read based on rule

2. Checking Write Permission

• Compares TS(T) with RTS(X) and WTS(X)
• Decides whether to allow or rollback

3. Transaction Rollback

• If rules are violated, transaction is aborted
• Restarted with a new timestamp

Detailed Example of Timestamp Ordering Protocol

Let’s Explain with an Example; look at the following table

Solution:

Draw the following table

In the above table, A, B, and C are data values. And  Read and Write timestamp values are given “0”. As in the example table, time0 to time7 are given. Let’s discuss it one by one.

At time 1, transaction 1 wants to perform a read operation on data “A.” then, according to Rule No 01,

• WTS(A) > TS(T1) = 0>100 // condition false
• Go to else part and SET RTS (A) = MAX {RTS(A), TS(T1)} So,
• RTS (A) = MAX{0,100}= 100.
• So, finally RTS(A) is updated with 100

The updated table will appear as follows,

At time 2, transaction 2 wants to perform a read operation on data “B.” then, according to Rule No 01,

• WTS(B) > TS(T2) = 0>200 // condition false
• Go to else part and SET RTS (B) = MAX {RTS(B), TS(T2)} So,
• RTS (B) = MAX{0,200} = 200.
• So, finally RTS(B) is updated with 200

The updated table will appear as follows,

At time 3, transaction 1 wants to perform a write operation on data “C.” then, according to Rule No 02,

• RTS(C) > TS(T1) = 0>100 // condition false
• Go to second condition, WTS(C) > TS(T1) = 0>100 // again condition false
• Go to the else part and SET WTS (C) = TS(T1) So,
• WTS (C) = TS(T1) = 100.
• So, finally WTS(C) is updated with 100

The updated table will appear as follows,

At time 4, transaction 3 wants to perform a read operation on data “B.” then, according to Rule No 01,

• WTS(B) > TS(T3) = 0>300 // condition false
• Go to else part and SET RTS (B) = MAX {RTS(B), TS(T3)} So,
• RTS (B) = MAX{200,300} = 300.
• So, finally, RTS(B) replaced 200 and updated it with 300.

The updated table will appear as follows,

At time 5,  the transaction T1 wants to perform a read operation on data “C” Then according to Rule No. 01,

• WTS(C) > TS(T1) = 100>100 // condition false
• Go to else part and SET RTS (C) = MAX {RTS(C), TS(T1)} So,
• RTS (A) = MAX{0,100}= 100.
• So, finally RTS(C) is updated with 100

The updated table will appear as follows,

At time 6, transaction 2 wants to perform a write operation on data “B.” then, according to Rule No 02,

• RTS(B) > TS(T2) = 300>200 // condition True

According to Rule 2, if the condition is true, then Rollback T2.

When T2 rolls, it never resumes. It will restart with a new timestamp value. Keep in mind that T2 restarts after completion of all running transactions, so in this example, T2 will restart after completion of T3.

It happens due to conflict where the older transaction (T2) wants to perform a write operation on data “B,” but the younger transaction (T3) has already Read the same data “B”

The table will remain the same

At time 7, transaction 3 wants to perform a write operation on data “A” Then according to Rule No 02,

• RTS(A) > TS(T3) = 100>300 // condition false
• Go to second condition, WTS(A) > TS(T3) = 100>300 // again condition false
• Go to the else part and SET WTS (A) = TS(T3) So,
• WTS (A) = 300.
• So, finally WTS(A) is updated with 300

An updated table will appear as follows,

Summary Table of Example Execution

Types of Timestamp Ordering Protocol

Different variations help improve efficiency and reduce rollbacks. The list of types is given below.

1. Basic Timestamp Ordering

• Strict rule enforcement
• High consistency
• More rollbacks

2. Thomas Write Rule

• Ignores outdated writes
• Reduces unnecessary aborts

3. Strict Timestamp Ordering

• Prevents reading uncommitted data
• Avoids cascading rollbacks

Advantages of Timestamp Ordering

Timestamp ordering offers several benefits in modern database systems. The list of advantages is given below.

1. Deadlock-Free

• No locks used

2. High Concurrency

• Multiple transactions execute simultaneously

3. Simple Logic

• Based on timestamp comparison

4. Ensures Serializability

• Maintains correct execution order

Disadvantages of Timestamp Ordering

Despite its strengths, it has some limitations. The list of disadvantages is given below.

1. Frequent Rollbacks

• Transactions restart often

2. Starvation

• Older transactions may never complete

3. Overhead

• Managing timestamps adds cost

4. Cascading Aborts

• Possible in basic protocol

Comparison Table: Timestamp Ordering vs Lock-Based Protocol

Conclusion of Timestamp Ordering

Timestamp Ordering is an efficient concurrency control method that ensures serializability using timestamps instead of locks. It is widely used in high-performance systems, but requires careful handling of rollbacks and starvation issues for optimal performance.