Intro to DBMS

Timestamp Ordering With Examples

As we already know, there are two rules for timestamp order. In this lecture, we will see an example of a time stamp ordering protocol.

Rule No. 01 is used when any transaction wants to perform a Read(A) operation

  • If WTS(A) > TS (Ti), then Ti Rollback
  • Else (otherwise) execute R(A) operation and SET RTS (A) = MAX {RTS(A), TS(Ti)}

Rules No.2 rules are used when a transaction needs to perform WRITE (A)

  • If RTS(A) > TS (Ti), then Ti Rollback
  • If WTS(A) > TS (Ti), then Ti Rollback
  • Else (otherwise) execute W(A) operation and SET WTS (A) = TS(Ti)

Where “A” is some data

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,