Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Timestamp-Based Protocol in DBMS
2.1.
Basic Time-stamp Ordering
2.1.1.
Read Operations
2.1.2.
Write Operations
2.1.3.
Thomas Write Rule
2.2.
Strict Time-stamp Ordering
2.3.
Advantages 
2.4.
Disadvantages 
3.
Frequently Asked Questions
3.1.
What is a cascadeless schedule?
3.2.
What is serializability?
3.3.
What is a concurrent execution of a transaction?
4.
Conclusion
Last Updated: Mar 27, 2024

Timestamp Based Protocol in DBMS

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The most commonly used concurrency protocol is the timestamp-based protocol. This protocol uses either system time or logical encounter as a time-stamp.

Lock-based protocols manage the order between the conflicting pairs among transactions at the time of execution, whereas timestamp-based protocols start working as soon as a transaction is created.  

Timestamp Based Protocol in DBMS

Every transaction has a time-stamp associated with it, and the age of the transaction determines the ordering. A transaction created at 0002 clock time would be older than all other transactions after it. For example, any transaction ‘y’ entering the system at 0004 is two seconds younger, and the priority would be given to the older one. 

Timestamp-Based Protocol in DBMS

Time-stamp is a unique identifier created by the DBMS to identify a transaction. —Each transaction is issued a time-stamp when it enters the system. If an old transaction Ti has time-stamp TS(Ti), a new transaction Tj is assigned time-stamp TS(Tj) such that TS(Ti) < TS(Tj).

In time-stamp order, the schedule is equivalent to the particular serial order corresponding to the order of the transaction time-stamps, unlike the lock-based technique where the schedule is made serial schedule based on locks.

The time-stamp ordering protocol ensures serializability among transactions in their conflicting read and writes operations. This is the responsibility of the protocol system that the conflicting pair of tasks should be executed according to the time-stamp values of the transactions.

  • The time-stamp of transaction Ti is denoted as TS(Ti)
     
  • Read time-stamp of data item X is denoted by R - time-stamp (X)
     
  • Write time-stamp of data-item X is denoted by W - time-stamp (X)
     
  • Time-stamp ordering protocol works as follows” If a transaction Ti issues a read(X) operation”
     
  • If a TS(T) < W-timestamp(X). Operation rejected
     
  • If TS(Ti) >= W-timestamp(X). Operation executed
     
  • All data-item time stamps are updated.
     
  • If a transaction Ti issues a write(X) operation
     
  • If TS(Ti) < R-timestamp(X). Operation rejected
     
  • If TS(Ti) < W-timestamp(X). Operation rejected and Ti rolled back. Otherwise, the operation is executed

Basic Time-stamp Ordering

The basic time-stamp ordering protocol (BASIC T/O) allows reads and writes on database objects without using locks. Instead, every database object X is tagged with a time-stamp of the last transaction that successfully performed a read (denoted as R-TS(X)) or write (denoted as W-TS(X)) on that object.
The DBMS then checks these time-stamps for every operation. If a transaction tries to access an object in a way that violates the time-stamp order, the transaction is aborted and restarted. The underlying assumption is that violations will be rare, and thus these restarts will also be rare. 

Read Operations

For read operations, if TS(Ti) < W-TS(X), this violates the time-stamp order of Ti with regard to the previous writer of X. Thus, Ti is aborted and restarted with a new time-stamp. 

Otherwise, the read is valid, and Ti is allowed to read X. The DBMS then updates R-TS(X) to be the max of R-TS(X) and TS(Ti). It also has to make a local copy of X to ensure repeatable reads for Ti.

Write Operations

For write operations, if TS(Ti) < R-TS(X) or TS(Ti) < W-TS(X), Ti must be restarted. Otherwise, the DBMS allows Ti to write X and updates W-TS(X). Again, it needs to make a local copy of X to ensure repeatable reads for Ti.

Thomas Write Rule

An optimization for writes is if TS(Ti) < W-TS(X), the DBMS can instead ignore the write and allow the transaction to continue instead of aborting and restarting it. This is called the Thomas Write Rule.

Note that this violates the time-stamp Ti's order of Ti. However, this is okay because no other transaction will ever read Ti’s write to object X. The Basic T/O protocol generates a conflict serializable schedule if it does not use Thomas Write Rule.

It cannot have deadlocks because no transaction ever waits. However, starvation for long transactions is possible if short transactions keep causing conflicts. It also permits schedules that are not recoverable. A schedule is recoverable if transactions commit only after all transactions whose changes they read commit. 

Otherwise, the DBMS cannot guarantee that transactions read data that will be restored after recovering from a crash.

Potential Issues: 

  • High overhead from copying data to the transaction’s workspace and updating time stamps. 
     
  • Long-running transactions can get starved. The likelihood that a transaction will read something from a newer transaction increases.
     
  • Suffers from the time-stamp allocation bottleneck on highly concurrent systems.

Strict Time-stamp Ordering

Timestamp-based concurrency control uses time stamps for synchronization instead of locks. From the outside, the transactions seem to be executed sequentially according to their starting time.

In other words, the scheduler generates serializable schedules equal to the serial execution of the transactions ordered by their starting time.

These time-stamps are used to guarantee the Time-stamp Ordering (TO) rule: if two operations pi(x) and qj (x) are in conflict, i.e., they access the same tuple x and at least one operation is a write operation, then the operation of the transaction with the lower time-stamp is always executed first. 

Thereby, the resulting schedule is equal to the serial execution of the transactions ordered by their time-stamp, and, as a consequence, it is serializable.

Time-stamp Ordering is called Strict Time-stamp Ordering (STO). STO does not only provide recoverable schedules but also strict schedules. That means no uncommitted changes of a running transaction are overwritten or read by another transaction. The use of a dirty bit prevents this.

Each transaction marks tuples with uncommitted changes by setting the dirty bit, and other transactions accessing such a tuple have to wait until the dirty bit is unset, which happens when the previous transaction commits or aborts.

Advantages 

  • The time-stamp ordering protocol ensures conflict serializability. This is because conflicting operations are processed in time-stamp order.
     
  • The timestamp-based protocol ensures freedom from deadlock since no transaction ever waits.

Disadvantages 

  • There is the possibility of starvation of long transactions. This may be due to a sequence of conflicting short transactions causing repeated restarting of the long transaction. One can avoid this by finding a transaction that restarts repeatedly, and conflicting transactions need to be temporarily blocked to enable the transaction to finish. 
     
  • The timestamp-based protocol may produce a schedule that is not recoverable. But one can make timestamp-based schedules recoverable.

Also read, File System vs DBMS

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a cascadeless schedule?

A cascade-less schedule is one where, for each pair of transactions, Ti and Tj, such that Tj reads a data item previously written by Ti, the commit operation of Ti appears before the read operation of Tj.

What is serializability?

Serializability is the classical concurrency scheme. It ensures that a schedule for executing concurrent transactions is equivalent to executing the transactions serially in some order.

What is a concurrent execution of a transaction?

Concurrent execution of transaction means multiple transactions execute/run concurrently in RDBMS, with each transaction doing its atomic unit of work for the operations encapsulated in the particular transaction.

Conclusion

Serializability is a minimum criterion for concurrent transactions scheme. Cascadeless and deadlock are inversely proportional to concurrency. To get more concurrency, the schedule must allow for deadlock and cascading rollback up to a certain extent. Time-stamp protocol ensures no deadlock since data items are locked before the execution of the transaction. 

To better understand the topic, refer to 
 

For more information, refer to our Guided Path on CodeStudio to upskill yourself in PythonData Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more! 
You can also consider our DBMS Course to give your career an edge over others.
 

Happy Learning!!

Previous article
Two-Phase Locking
Next article
Conservative 2-Phase Locking
Live masterclass