Hello students! Today I brought you another interesting article. Hope you are doing in your studies. Earlier we have discussed about concurrency control techniques. There we told we have two techniques. They are locking and timestamping. We discussed about locking concept. If you missed it here’s the post. Database Locking. From this post we are going to discuss about timestamping in database management system. Without wasting time furthermore we will start the lesson.
What is timestamping in databases
Timestamping method is a success method than locking. In locking we saw different locking types. There we saw different limitations like deadlocks and starvation. Timestamping does not have that type of limitations.
Timestamping is a monotonically increasing value. It contains the largest timestamp of the transaction which has successfully read the transaction. Timestamping concept is something like this. If we take a real world example. A doctor has many patients. Those patients has a number. According to the number order patients visit the doctor. In timestamp concept something happens. All the transactions will get a timestamp. To that order they can perform the execution. Timestamp means not a number. It has complete time details Like date, time with seconds. Hence timestamp of two transactions cannot be same.
Timestamps we have in a database
We maintain two timestamp types in the databases. They are read and write timestamp. Now let’s see what they are,
Read Timestamp – This timestamp indicates the largest timestamp which successfully read that data item.
Write Timestamp – This timestamp indicates the largest timestamp which successfully read that data item.
Timestamp Algorithms
Timestamping concept works on the basis of a algorithm. In order to understand timestamp concept and answer questions Firstly we have to understand the algorithms. We have two algorithms. For read and write operations separately. Let’s look at algorithms.
Read Algorithm
IF (WT > TS(T)){
abort;
}
else{
Read & [update RT]
}
Before explain the algorithm Let’s identify the terms first.
WT – Write Timestamp
TS(T) – Timestamp of the transaction
RT – Read Timestamp
Now let’s see the explanation.
In the IF statement says to compare two values. Those two values are write timestamp and transaction timestamp which is going to read the data item. If write timestamp value is grater than transaction timestamp we don’t allow to perform the operation. If not we allow the operation. Then read timestamp would be updated. If you remember read and write timestamp contains the largest value of transaction lastly read. When transactions comes in the ascending order lastly read timestamp value cannot be grater then current timestamp value. When a transaction successfully perform read or write it update the respective timestamp value.
As a summary what you have to know is. There are two timestamp values. They are read and write timestamp. All the transactions also have a timestamp. Above mentioned two timestamps store the timestamp of the transaction lastly successfully perform that operation. Furthermore read timestamp stores the timestamp of transaction which successfully read item X. Write timestamp contains the timestamp of the transaction which lastly successfully write that item X.
Write Algorithm
IF (WT > TS(T) || RT > TS(T)){
abort; }
Else{
Write & [Update WT]
}
Let’s move to the explanation. In the IF statement like previous algorithm two conditions are checked. One is Write timestamp value and transaction value. Other one is read timestamp and transaction value. If both combination false else statement will executed. from else statement write timestamp value will updated. Either conditions true in the IF statement will leads to abort the operation because it’s OR condition. Do you remember the earlier topics and details we discussed. Can you answer this question? What are the conflict operation types in a transaction schedule? Do you remember the answer. This is the answer.
The conflict operations in a database transaction schedule as follows. Read – write, write – read, write – write. If you clearly see you will notice something. That something is read operations have conflicts from write operations only. Write operations have conflicts from both read and write operations. Because of that in read algorithm we only check the write timestamp value. In write algorithm we check both read and write algorithm.
As a summary of transaction algorithm here’s the brief you have to memorize. This will help you to clear doubts. We learn the big picture. Before moving to an application let’s first brief what we have learn. In timestamp ordering we maintain two timestamps. Every transactions have a timestamp. The two timestamps are the write timestamp and read time stamp. Write timestamp stores the largest timestamp of the transaction which successfully lastly write a data item. Read timestamp stores the timestamp of the transaction which successfully lastly read that data item successfully.
Example for timestamp ordering
Firstly let’s see the terms we need. There are four transactions. Their operations and timestamps are as below.
Ta – Read (X) – 100
Tb – Write (X) – 101
Tc – Read (X) – 102
Td – Write (X) – 103
In the beginning write timestamp value – 0
In the beginning read timestamp value – 0
Combination for read operation – WT > TS
Combination for write operation – WT > TS || RT > TS
Now we’ll see the execution process.
Transaction Ta enters
The first transaction get opportunity to work with data items is Ta. Since it has the lowest timestamp. That means it came early. It has to finish execution also first. Let’s turn to the algorithm and compare values. WT > TS. Write timestamp value is 0. Transaction timestamp is 100. 0>100 statement is false. Then else statement execute. According to the else statement transaction can perform the operation and read timestamp now updated to the 100.
After Ta write timestamp value – 0
After Ta read timestamp value – 100
Transaction Tb enters
When Tb enters Tb has a write operation. Let’s put values and see the algorithm. Write timestamp value is 0. Read timestamp value is 100. Transaction timestamp is 101. WT > TS || RT > TS [0>101 || 100>101]. 0>101 is also false. 100>101 is also false. Then else statement execute. So transaction successfully read the data item then write timestamp updated.
After Tb write timestamp value – 101
After Tb read timestamp value – 100
Transaction Tc enters
Let’s assume Tc missed it’s change. So transaction Td start to execute.
Transaction Td enters
When Td starts. As same as above we did put to the algorithm and see. WT > TS || RT > TS [101>104 || 100>104]. Both the condition false. Therefore transaction successfully write the data item and write stamp updated.
After Td write timestamp value – 104
After Td read timestamp value – 100
Now let’s assume Tc enters after Td executed.
Transaction Tc enters
Tc has a read operation. Let’s put it to the read algorithm and see. WT > TS [104>103]. 104 > 103 is true. So IF statement will execute. According to the IF statement Since write timestamp value is grater than transaction timestamp value operation will abort. Then what happen to Tc. It has to come with new timestamp.
Transaction Tc enters with new timestamp
Now Tc timestamp value is 105. Let’s put to the algorithm and check. WT > TS [104>105]. Now the condition is false and transaction allow to read the data item. Then read timestamp will updated.
After Tc write timestamp value – 104
After Tc read timestamp value – 105
Tc has to abort the transaction and come up with a new timestamp was happened because of Td operation. Td operation was a write operation. You know write operation and read operation has conflict. That’s why Tc has to abort. Now let’s assume Td operation was also a read operation. Then Read timestamp is 104. Write timestamp is 102. Let’s put the algorithm again. WT > TS [102>103]. Now this combination is false and Tc allow to read the data item although it missed the slot. But here timestamp value will not updated. If you see read timestamp value is 104. Current read operation performed transaction timestamp is 103. Yet the timestamp wouldn’t update to 103 since timestamp always contains the largest value. Do you remember the definition. Timestamp contains the largest timestamp value of successfully read or write operation performed transaction.
Conclusion
As always now we have come to the end of our post. These are the things you need to know about timestamp concept. I hope this article helped you to understand the timestamp theories. Today we have discussed general example of timestamping. Timestamping questions solving mechanism is little bit different. You can’t apply this algorithm direct. There is a little secret. You have to maintain read and write timestamps for each data item. So I hope to write another article by explaining a timestamping question and multiversioning. Multivertioning is also a simple concept that you need to know.
As always If this post help you please give us a comment and share it among your friends. They also can learn. If you need to clear more topics please comment and let us know. We can write a post about it. We have a collection of posts related to database concepts. If you interested please have a look. Transaction schedule and serializability is one of them. Let’s meet with another interesting topic. Till then good bye! Have a nice day!
