Lab 8: Timestamp-based concurrency control

request	response	state changes and/or explanation
r1(Y)	allowed	RTS(Y) = 100
w2(Y)	allowed	WTS(Y) = 200
w2(X)	allowed	WTS(X) = 200
r3(Z)	allowed	RTS(Z) = 300
r2(Z)	allowed	RTS is not changed (see below)
w3(Y)	allowed	WTS(Y) = 300
r3(X)	allowed	RTS(X) = 300
w1(Y)	ignored	TS(T1) >= RTS(Y) but TS(T1) < WTS(Y)
r1(X)	denied; roll back	TS(T1) < WTS(X); RTS(Y) = 0

Here are some additional notes about each request:

1. r1(Y):

   • test: TS(T1) ≥ WTS(Y), 100 ≥ 0, true, so allow
   • change: RTS(Y) = max(RTS(Y),TS(T1)) = max(0,100) = 100

2. 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

3. 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

4. r3(Z):

   • test: TS(T3) ≥ WTS(Z), 300 ≥ 0, true, so allow
   • change: RTS(Z) = max(RTS(Z),TS(T3)) = max(0,300) = 300

5. r2(Z):

   • test: TS(T2) ≥ WTS(Z), 200 ≥ 0, true, so allow
   • 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.

6. 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
   • 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 timsteamp ordering than the writer of the previous value.

7. r3(X):

   • test: TS(T3) ≥ WTS(X), 300 ≥ 200, true, so allow
   • change: RTS(X) = max(RTS(X),TS(T3)) = max(200,300) = 300
   • Note that that this is a dirty read, because the writer of the prior value of X (T2) has not yet committed. Without the use of commit bits, dirty reads may occur!

8. w1(Y):

   • first test: TS(T1) ≥ RTS(Y), 100 ≥ 100, true
   • second test: TS(T1) ≥ WTS(Y), 100 ≥ 300, false, so ignore
   • 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.

9. 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.

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

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)	now 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:

1. r1(Y): same as before, but we also check that c(Y) == true before allowing the read.

2. w2(Y): same as before, but we also set c(Y) to false to indicate that the writer of Y has not yet committed.

3. w2(X): same as before, but we also set c(X) to false.

4. r3(Z): same as before, but we also check that c(Z) == true before allowing the read

5. r2(Z): same as before, but we also check that c(Z) == true.

6. w3(Y): same as before; c(Y) remains true, and T3 becomes Y’s most recent writer.

7. r3(X):

   • first test: TS(T3) ≥ WTS(X), 300 ≥ 200, true
   • second test: check c(X), it’s false so deny and make wait
   • Since X’s commit bit is false, we know that the writer of its current value has not yet committed. Thus, T3 is made to wait to avoid a dirty read.

8. 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.

9. r3(X): now that c(X) is true, T3 is allowed to try again and the read is allowed.

10. c3: T3 commits.

    • c(Y) is set to true because T3 is the writer of Y’s current value.

11. w1(Y):

    • first two tests: same as before
    • third test: c(Y) is true, so ignore
    • 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.

12. r1(X):

    • test: TS(T1) ≥ WTS(X), 100 ≥ 200, false, so deny and roll back
    • since T1 is the latest reader of Y (RTS(Y) == 100), we restore RTS(Y) to its prior value of 0.

13. c1: T1 has already been rolled back, so this action doesn’t occur.

To prevent rollbacks that stem from reading an item.

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
w1(Y)	allowed	create Y(100) with RTS = 0
r1(X)	allowed to read X(0)	RTS(X(0)) = 100

Here are some additional notes about each request:

1. 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

2. 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.

3. 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

4. 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

5. 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.

6. 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

7. 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

8. w1(Y):

   • there are three versions of Y: Y(0), Y(200) and Y(300)
   • based on its timestamp, T1 should be overwriting Y(0)
   • only test: TS(T1) ≥ RTS(Y(0)), 100 ≥ 100, true, so allow
   • a new version Y(100) is created with RTS = 0

9. r1(X):

   • T1 should read X(0), and it is allowed to do so!
   • reads never lead to rollbacks when there are multiple versions.
   • change: RTS(X(0)) = max(RTS(X(0),TS(T1)) = max(0,100) = 100