Repeat Exercise 22.25, but use the multiversion timestamp ordering method.

Question

Fill in the blank(s) with the appropriate word(s).

Answer 1

Let us assume the same timestamp values as in the solution for Exercise 18.22 above. To refer to versions, we use X, Y, Z to reference the original version (value) of each item, and then use indexes (1, 2, ...) to refer to newly written version (for example, X1, X2, ...).

(a) Applying multiversion timestamp ordering to Schedule E:
Initial values (new values are shown after each operation):
read_TS(X)=0,read_TS(Y)=0,read_TS(Z)=0,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
TS(T1)=6, TS(T2)=1, TS(T3)=4 (These do not change)
T2: read_item(Z)
Execute read_item(Z)
Set read_TS(Z) <- max(read_TS(Z),TS(T2)) = 1
read_TS(X)=0,read_TS(Y)=0,read_TS(Z)=1,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
T2: read_item(Y)
Execute read_item(Y)
Set read_TS(Y) <- max(read_TS(Y),TS(T2)) = 1
read_TS(X)=0,read_TS(Y)=1,read_TS(Z)=1,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
T2: write_item(Y)
TS(T2) = read_TS(Y)
Execute write_item(Y) (by creating a new version Y1 of Y)
write_TS(Y1) <- TS(T2) = 1,
read_TS(Y1) <- TS(T2) = 1
read_TS(X)=0,read_TS(Y)=1,read_TS(Y1)=1,read_TS(Z)=1,
write_TS(X)=0,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0
T3: read_item(Y)
Execute read_item(Y) by reading the value of version Y1
read_TS(Y1) <- max(read_TS(Y1),TS(T3)) = 4
read_TS(X)=0,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Z)=1,
write_TS(X)=0,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0
T3: read_item(Z)
Execute read_item(Z)
read_TS(Z) <- max(read_TS(Z),TS(T3)) = 4
read_TS(X)=0,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Z)=4,
write_TS(X)=0,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0
T1: read_item(X)
Execute read_item(X)
read_TS(X) <- max(read_TS(X),TS(T1)) = 6
read_TS(X)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Z)=4,
write_TS(X)=0,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0
T1: write_item(X)
Execute write_item(X) (by creating a new version X1 of X)
write_TS(X) <- TS(T1) = 6,
read_TS(X) <- TS(T1) = 6
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Z)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0
T3: write_item(Y)
Execute write_item(Y) (by creating a new version Y2 of Y)
write_TS(Y2) <- TS(T3) = 4,
read_TS(Y2) <- TS(T3) = 4
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=4,
read_TS(Z)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
write_TS(Z)=0
T3: write_item(Z)
Execute write_item(Z) (by creating a new version Z1 of Z)
write_TS(Z1) <- TS(T3) = 4,
read_TS(Z1) <- TS(T3) = 4
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=4,
read_TS(Z)=4,read_TS(Z1)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
write_TS(Z)=0,write_TS(Z1)=4
T2: read_item(X)
Execute read_item(X) by reading the value of the initial version X
read_TS(X) <- max(read_TS(X),TS(T3)) = 6
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=4,
read_TS(Z)=4,read_TS(Z1)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
write_TS(Z)=0,write_TS(Z1)=4
T1: read_item(Y)
Execute read_item(Y) by reading the value of version Y2
read_TS(Y2) <- max(read_TS(Y2),TS(T3)) = 6
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=6,
read_TS(Z)=4,read_TS(Z1)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
write_TS(Z)=0,write_TS(Z1)=4
T1: write_item(Y)
Execute write_item(Y) (by creating a new version Y3 of Y)
write_TS(Y3) <- TS(T3) = 4,
read_TS(Y2) <- TS(T3) = 4
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=6,
read_TS(Y3)=6,read_TS(Z)=4,read_TS(Z1)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
write_TS(Y2)=6,write_TS(Z)=0,write_TS(Z1)=4
T2: write_item(X)
Abort and Rollback T2 since read_TS(X) >TS(T2)

Result: Since T3 had read the value of Y that was written by T2, T3 should also be aborted
and rolled by the recovery technique (because of cascading rollback); hence, all effects of T2
and T3 would also be erased and only T1 would finish execution.

(b) Applying timestamp ordering to Schedule F:
Initial values (new values are shown after each operation):
read_TS(X)=0,read_TS(Y)=0,read_TS(Z)=0,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
TS(T1)=3, TS(T2)=7, TS(T3)=1 (These do not change)
T3: read_item(Y)
Execute read_item(Y)
Set read_TS(Y) <- max(read_TS(Y),TS(T3)) = 1
read_TS(X)=0,read_TS(Y)=1,read_TS(Z)=0,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
T3: read_item(Z)
Execute read_item(Z)
Set read_TS(Z) <- max(read_TS(Z),TS(T3)) = 1
read_TS(X)=0,read_TS(Y)=1,read_TS(Z)=1,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
T1: read_item(X)
Execute read_item(X)
read_TS(X) <- max(read_TS(X),TS(T1)) = 3
read_TS(X)=3,read_TS(Y)=1,read_TS(Z)=1,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
T1: write_item(X)
Execute write_item(X) by creating a new version X1 of X
write_TS(X1) <- TS(T1) = 3, read_TS(X1) <- TS(T1) = 3
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=1,read_TS(Z)=1,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Z)=0
T3: write_item(Y)
Execute write_item(Y) by creating a new version Y1 of Y
write_TS(Y1) <- TS(T3) = 1, read_TS(Y1) <- TS(T3) = 1
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=1,read_TS(Y1)=1,read_TS(Z)=1,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0
T3: write_item(Z)
Execute write_item(Z) by creating a new version Z1 of Z
write_TS(Z1) <- TS(T3) = 1, read_TS(Z1) <- TS(T3) = 1
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=1,read_TS(Y1)=1,read_TS(Z)=1,
read_TS(Z1)=1,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0,
write_TS(Z1)=1
T2: read_item(Z)
Execute read_item(Z) by reading the value of version Z1
Set read_TS(Z1) <- max(read_TS(Z1),TS(T2)) = 7
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=1,read_TS(Y1)=1,read_TS(Z)=1,
read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0,
write_TS(Z1)=1
T1: read_item(Y)
Execute read_item(Y) by reading the value of version Y1
Set read_TS(Y1) <- max(read_TS(Y1),TS(T1)) = 3
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Z)=1,
read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Z)=0,
write_TS(Z1)=1
T1: write_item(Y)
Execute write_item(Y) by creating a new version Y2 of Y
write_TS(Y2) <- TS(T1) = 3, read_TS(Y2) <- TS(T1) = 3
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Y2)=3,
read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=3,
write_TS(Z)=0,write_TS(Z1)=1
T2: read_item(Y)
Execute read_item(Y) by reading the value of version Y2
Set read_TS(Y2) <- max(read_TS(Y2),TS(T2)) = 7
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Y2)=7,
read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=3,
write_TS(Z)=0,write_TS(Z1)=1
T2: write_item(Y)
Execute write_item(Y) by creating a new version Y3 of Y
write_TS(Y3) <- TS(T2) = 7, read_TS(Y3) <- TS(T2) = 7
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Y2)=7,
read_TS(Y3)=7,read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=3,
write_TS(Y3)=7,write_TS(Z)=0,write_TS(Z1)=1
T2: read_item(X)
Execute read_item(X) by reading the value of version X1
Set read_TS(X1) <- max(read_TS(X1),TS(T2)) = 7
read_TS(X)=3,read_TS(X1)=7,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Y2)=7,
read_TS(Y3)=7,read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=3,
write_TS(Y3)=7,write_TS(Z)=0,write_TS(Z1)=1
T2: write_item(X)
Execute write_item(X) by creating a new version X2 of X
write_TS(X2) <- TS(T2) = 7, read_TS(X2) <- TS(T2) = 7
read_TS(X)=3,read_TS(X1)=7,read_TS(X2)=7,read_TS(Y)=3,read_TS(Y1)=1,
read_TS(Y2)=7,read_TS(Y3)=7,read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(X2)=7,write_TS(Y)=0,write_TS(Y1)=1,
write_TS(Y2)=3,write_TS(Y3)=7,write_TS(Z)=0,write_TS(Z1)=1

Result: Schedule F executes successfully.