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,
