Lab 8: Timestamp-based concurrency control

Preliminaries
Exercise 1: commit bits; one version of each data item
Exercise 2: no commit bits; multiple versions of each data item

Preliminaries

We will be analyzing schedules of transactions in a system that uses some form of timestamp-based concurrency control.

In each exercise, there are three transactions (T1, T2 and T3) and three data items (X, Y and Z).

You should assume that:

The read and write timestamps of all of the data items are initially 0.
The timestamps assigned to the transactions are:
- TS(T1) = 100
- TS(T2) = 200
- TS(T3) = 300
These timestamps are consistent with the fact that, in the schedules we’ll be analyzing below, T1 starts first, followed by T2, followed by T3.

In giving your answers, you should fill in a table that begins as follows:

request	response	state changes and/or explanation
r1(Y)	allowed	RTS(Y) = 100

The third column should include any changes to the state maintained for the data item. If a request is denied or ignored, that column should also include a brief explanation of why.

You do not need to restart a transaction that is rolled back, which means that you can skip any requests by a transaction that come after the point at which it is rolled back.

Exercise 1: commit bits; one version of each data item

In this exercise, we will assume that the DBMS is using timestamp-based concurrency control with commit bits and with only one version of each data item.

What is the purpose of maintaining commit bits?

To prevent dirty reads, and to thereby produce schedules that are recoverable and cascadeless.

Consider the following schedule:

s1; r1(Y); s2; w2(Y); w2(X); s3; r3(Z); r2(Z); w3(Y); r3(X); c2; c3; w1(Y); r1(X); c1

How would the system respond to each of the requested actions?

In addition to the assumptions mentioned in the preliminaries, you should assume that all of the commit bits are initially true.
Make sure to include the responses to the commit requests (c1, c2, c3), since they are relevant when a system uses commit bits.
If a transaction is made to wait, you should include the relevant request a second time when the transaction is allowed to try again.

request	response	state changes and/or explanation
r1(Y)	allowed	RTS(Y) = 100
w2(Y)	allowed	WTS(Y) = 200, c(Y) = false
w2(X)	allowed	WTS(X) = 200, c(X) = false
r3(Z)	allowed	RTS(Z) = 300
r2(Z)	allowed	RTS is not changed (see below)
w3(Y)	allowed	WTS(Y) = 300, C(Y) remains false
r3(X)	denied; make wait	TS(T3) >= WTS(X) but c(X) == false
c2	allowed	c(X) = true
r3(X)	allowed!	RTS(X) = 300
c3	allowed	c(Y) = true
w1(Y)	ignored	TS(T1) >= RTS(Y) but TS(T1) < WTS(Y)
		and c(Y) == true
r1(X)	denied; roll back	TS(T1) < WTS(X); RTS(Y) = 0
c1	doesn’t happen	T1 has already been rolled back

Here are some additional notes about each request:

r1(Y):
- test: TS(T1) ≥ WTS(Y), 100 ≥ 0, true
- second test: c(Y) is true, so allow the read without a wait
- change: RTS(Y) = max(RTS(Y),TS(T1)) = max(0,100) = 100
- Note: If we weren’t using commit bits, we wouldn’t need the second test, and the read would be allowed as long as the first test is passed.
w2(Y):
- first test: TS(T2) ≥ RTS(Y), 200 ≥ 100, true
- second test: TS(T2) ≥ WTS(Y), 200 ≥ 0, true, so allow
- change: WTS(Y) = TS(T2) = 200
- we also set c(Y) to false to indicate that the writer of Y’s current value has not yet committed
w2(X):
- first test: TS(T2) ≥ RTS(X), 200 ≥ 0, true
- second test: TS(T2) ≥ WTS(X), 200 ≥ 0, true, so allow
- change: WTS(X) = TS(T2) = 200
- we also set c(X) to false to indicate that the writer of X’s current value has not yet committed
r3(Z):
- test: TS(T3) ≥ WTS(Z), 300 ≥ 0, true
- second test: c(Z) is true, so allow the read without a wait
- change: RTS(Z) = max(RTS(Z),TS(T3)) = max(0,300) = 300
r2(Z):
- test: TS(T2) ≥ WTS(Z), 200 ≥ 0, true
- second test: c(Z) is true, so allow the read without a wait
- change: RTS(Z) = max(RTS(Z),TS(T3)) = max(300,200) = 300
- Note that the RTS doesn’t change in this case! The RTS is not necessarily the timestamp of the most recent reader. Rather, it is the timestamp of the reader that comes latest in the equivalent serial schedule. These values may not be the same because reads don’t conflict with each other and thus they don’t need to follow the timestamp ordering.
w3(Y):
- first test: TS(T3) ≥ RTS(Y), 300 ≥ 100, true
- second test: TS(T3) ≥ WTS(Y), 300 ≥ 200, true, so allow
- change: WTS(Y) = TS(T3) = 300
- c(Y) remains true, and T3 becomes Y’s most recent writer.
- Note that the WTS is always the timestamp of the most recent writer, since writes are only allowed if they follow the timestamp ordering – i.e., if the transaction requesting the write comes later in the timestamp ordering than the writer of the previous value.
r3(X):
- test: TS(T3) ≥ WTS(X), 300 ≥ 200, true
- second test: c(X) is false, so make T3 wait, which prevents what would otherwise be a dirty read, because the writer of the prior value of X (T2) has not yet committed.
- If we weren’t using commit bits, this read would be allowed!
c2: T2 commits
- c(X) is set to true because T2 is the writer of X’s current value.
- Note that we do not set c(Y) to true. T2 did write Y, but T3 overwrote that value, so T2 is not the writer of Y’s current value.
- If we weren’t using commit bits, we could ignore the commits, since they aren’t relevant in the absence of commit bits
r3(X): now that c(X) is true, T3 is allowed to try again and the read is allowed.
c3: T3 commits.
- c(Y) is set to true because T3 is the writer of Y’s current value.
w1(Y):
- first test: TS(T1) ≥ RTS(Y), 100 ≥ 100, true
- second test: TS(T1) ≥ WTS(Y), 100 ≥ 300, false, so don’t allow
- third test: c(Y) is true, so ignore the write.
- Note that the write cannot be allowed, because the current value of Y was written by T3, which comes after T1 in the equivalent serial schedule based on the timestamps. The DBMS ignores the request—treating T1’s write as if it occurred before the write by T3 and was overwritten.
- Note: If c(Y) were false in this case, T1 would be made to wait, since the value that it wants to write may be needed if (1) the writer of Y’s current value is rolled back and (2) there is another transaction waiting to read Y when the rollback occurs.
- If we weren’t using commit bits, we wouldn’t need the third test to know that we should ignore the write.
r1(X):
- test: TS(T1) ≥ WTS(X), 100 ≥ 200, false, so deny and roll back
- Note that the WTS tells us that T2 wrote the current value of X. T1 comes before T2 in the equivalent serial schedule, so it should have read the original value of X instead of its current value. Thus, this read cannot be allowed. The system rolls back T1 and will later restart it with a larger timestamp.
- Since T1 is the latest reader of Y (RTS(Y) == 100), we restore RTS(Y) to its prior value of 0.
c1: T1 has already been rolled back, so this action doesn’t occur.

Exercise 2: no commit bits; multiple versions of each data item

In this exercise, we will assume that the DBMS is using timestamp-based concurrency control without commit bits and with multiple versions of each item.

What is the purpose of maintaining multiple versions?

To prevent rollbacks that stem from reading an item.

Consider the following schedule (which is slightly different than the one from Exercise 1):

s1; r1(Y); s2; w2(Y); w2(X); s3; r3(Z); r2(Z); w3(Y); r3(X); c2; c3; r1(X); w1(Z); c1

How would the system respond to each of the requested actions?

You should make the same assumptions as before about the timestamps of the transactions and the initial timestamps of the data items.
Make sure to create a new version of a data item whenever necessary.
Because commits don’t have an effect when we’re not using commit bits, you do not need to include the commit actions (c1, c2, etc.) in your table.

request	response	state changes and/or explanation
r1(Y)	allowed to read Y(0)	RTS(Y(0)) = 100
w2(Y)	allowed	create Y(200) with RTS = 0
w2(X)	allowed	create X(200) with RTS = 0
r3(Z)	allowed to read Z(0)	RTS(Z(0)) = 300
r2(Z)	allowed to read Z(0)	RTS(Z(0)) is unchanged
w3(Y)	allowed	create Y(300) with RTS = 0
r3(X)	allowed to read X(200)	RTS(X(200)) = 300
r1(X)	allowed to read X(0)	RTS(X(0)) = 100
w1(Z)	denied; rollback	RTS(X(0)) = 0; RTS(Y(0)) = 0

Here are some additional notes about each request:

r1(Y):
- test: none, because reads are always allowed when there are multiple versions!
- the DBMS finds the appropriate version for T1 to read based on its timestamp, which in this case is the original version, Y(0)
- change: RTS(Y(0)) = max(RTS(Y(0),TS(T1)) = max(0,100) = 100
w2(Y):
- start by finding the version of Y that T2 should be overwriting based on its timestamp, which in this case is Y(0)
- only test: TS(T2) ≥ RTS(Y(0)), 200 ≥ 100, true, so allow
- the write creates a new version of Y, Y(200) – i.e., a version of T whose WTS is 200. The RTS of the new version is initially 0.
- note that we don’t need to compare TS(T2) to WTS(Y), because writes are never ignored when there are multiple versions
w2(X):
- T2 should be overwriting X(0)
- only test: TS(T2) ≥ RTS(X(0)), 200 ≥ 0, true, so allow
- a new version X(200) is created with RTS = 0
r3(Z):
- the DBMS finds the appropriate version for T3 to read based on its timestamp, which in this case is the original version, Z(0)
- change: RTS(Z(0)) = max(RTS(Z(0),TS(T3)) = max(0,300) = 300
r2(Z):
- T2 should read Z(0)
- no state change, since T2 isn’t the reader of Z(0) that comes latest in the timestamp ordering.
w3(Y):
- there are two versions of Y: Y(0) and Y(200)
- based on its timestamp, T3 should be overwriting Y(200)
- only test: TS(T3) ≥ RTS(Y(200)), 300 ≥ 0, true, so allow
- a new version Y(300) is created with RTS = 0
r3(X):
- there are two versions of X: X(0) and X(200)
- based on its timestamp, T3 should be reading X(200)
- change: RTS(X(200)) = max(RTS(X(200),TS(T3)) = max(0,300) = 300
r1(X):
- there are two versions of X: X(0) and X(200)
- based on its timestamp, T1 should read X(0)
- change: RTS(X(0)) = max(RTS(X(0),TS(T1)) = max(0,100) = 100
w1(Z):
- there is only one version of Z: Z(0)
- only test: TS(T1) ≥ RTS(Z(0)), 100 ≥ 300, false, so deny and roll back.
- In the equivalent serial schedule based on the timestamps, T3 (and T2 as well!) should have read the version of Z that T1 wants to write, but they didn’t, so T1’s write is too late.
- We review all of the versions of the data items, and we see that RTS(X(0)) and RTS(Y(0)) both equal TS(T1). Therefore, as part of rolling back T1, we restore the previous RTS values of those versions.

Last updated on April 3, 2025.