Lock-Based Concurrency Control - Transaction Processing - page 139

to the inserted key y 0 for I 2 Œy 0 or a short-duration X lock on the deleted key y for
D 2 Œy or a commit-duration X lock on the key y to be restored to the database for
I 1

2 Œy.Also,o 2 Œy 0 cannot be an undo-delete action D 2 Œy 0 with y>y 0 x by a
transaction T 2 6D T 1 , because then the key next to y 0 would be y and so Lemma 6.10
would imply that T 2 must hold a commit-duration X lock on y. Thus we conclude
that o 2 Œy 0 can only be an action by T 1 itself.
As LJ 0 contains no undo actions by T 1 , the action o 2 Œy 0 can only be an insert
action IŒy 0 or a delete action DŒy by T 1 . In the case of an insert action IŒy 0 with
y>y 0 x, T 1 holds a commit-duration X lock on the least key y 0 x,byrule
(2). In the case of a delete action DŒy, T 1 holds, by rule (3), a commit-duration
Xlockonthekeynexttoy, which is then also the key next to x. Because the least
key x remains the same through LJ 2 , we conclude that in each case T 1 holds a
commit-duration X lock on the least key x in the database at H 0 and hence also
at H . t

Lemma 6.12 Assume that a history H is permitted by the rules (2)-(7) of the key-
range locking protocol on a given database. Then H contains no dirty writes.

Proof For the sake of contradiction, assume that H contains a dirty write. By
Lemma 5.13 , we can write H as
H D ˛o 1 ŒxLJo 2 Œx D H 0 o 2 Œx ,
where o 1 Œx is a forward-rolling insert action I 1 Œx or delete action D 1 Œx by some
transaction T 1 active at H 0 , o 2 Œx is a forward-rolling insert action I 2 Œx or delete
action D 2 Œx by some transaction T 2 other than T 1 , and the action sequence LJ does
not contain the corresponding undo action for o 1 Œx.
By Lemma 6.11 , T 1 holds a commit-duration X lock on the least key y x at
H 0 , that is, on x if x is in the database at H 0 andonthekeynexttox if x is not in
the database at H 0 . Moreover, in the case o 1 Œx D I 1 Œx, T 1 holds a commit-duration
Xlockonx at H 0 , by rule (2) of the key-range locking protocol. Note that rule (6)
does not apply for T 1 and o 1 Œx, because T 1 does not undo o 1 Œx in LJ.
In the case o 2 Œx D I 2 Œx, x is not in the database at H 0 , y is the key next to x,and
T 2 must acquire at H 0 a commit-duration X lock on x and a short-duration X lock
on y, by rule (2). In the case o 2 Œx D D 2 Œx, x is in the database at H 0 , y D x,and
T 2 must acquire at H 0 a short-duration X lock on x (and a commit-duration X lock
on the key next to x), by rule (3).
We conclude the impossibility of all the following cases:

Case (a) o 1 Œx D I 1 Œx and o 2 Œx D I 2 Œx.ThenT 1 holds a commit-duration
Xlockonx at H 0 ,andT 2 should acquire a commit-duration X lock on x.
Case (b) o 1 Œx D I 1 Œx and o 2 Œx D D 2 Œx.ThenT 1 holds a commit-duration
Xlockonx at H 0 ,andT 2 should acquire a short-duration X lock on x.
Case (c) o 1 Œx D D 1 Œx and o 2 Œx D I 2 Œx.Thenx is not in the database at H 0 ,
T 1 holds a commit-duration X lock on the key y next to x at H 0 ,andT 2 should
acquire a short-duration X lock on y.