Lock-Based Concurrency Control - Transaction Processing - page 137

different) next key of x will be locked. For example, it is not immediately obvious
that the history

T 1 : ::: DŒx :::

T 2 : ::: IŒx :::

(exhibiting a dirty write) is prevented by the rules (2) and (3) of the key-range
locking protocol. This is because, though the key next to x is X-locked by T 1 for
commit duration when performing the delete action DŒx,thekeynexttox may
have changed by the time T 2 wants to execute its insert action IŒx. In Lemmas 6.10
and 6.11 , we prove that in such a case T 1 always holds an X lock on the current next
key of x.

Lemma 6.10 Assume that a history H is permitted by the rules (2)-(7) of the key-
range locking protocol on a given database. Then for any undo-delete action D 1 Œx
in H the key next to x in the database at the time the action is performed is the same
as the key next to x in the database at the time the corresponding forward-rolling
delete action DŒx was performed.

Proof The proof is by induction on the number of undo-delete actions in H .The
claim holds trivially in the base case in which H contains no undo-delete actions.
In the induction step we consider the last undo-delete action in H and write H as
H D ˛D i ŒxLJD 1

Œx;

i

where D i Œx is the delete action by transaction T i corresponding to the undo-delete
action D i Œx by T i and contains no undo-delete actions. Let y be the key
next to x in the database at ˛D i Œx and y 0 the key next to x in the database at
˛D i ŒxLJD i Œx. We have to prove that y 0 D y. By rule (3) of the key-range locking
protocol, T i holds a commit-duration X lock on y.
First we note that if the transaction T i itself changes the key next to x between
the database states at ˛D i Œx and at ˛D i ŒxLJD 1

i Œx, then those changes are undone
before performing D i Œx. Thus if y 0 6D y, some actions in the sequence LJ by
transactions other than T i are responsible for the change, although those actions
may be intermixed with actions of T i in LJ.
Changing y to y 0 by a sequence of one or more actions can only be accomplished
by deleting y or by inserting some key z with x< z <y. Because of the commit-
duration X lock held by T i on y, the sequence LJ cannot contain any delete action
D j Œy or insert action I j Œ z by a transaction T j other than T i with x z <y(by
rules (2) and (3)). Also an undo-insert action I 1
j

Œy in LJ is impossible because T j

cannot hold a commit-duration X lock on y.
There remains the case in which LJ contains an undo-delete action D j Πz that
inserts a key z between x and y. The history ˛D i ŒxLJ has one undo-delete action
less than H . By the induction hypothesis, the key next to z in the database at the
time the corresponding forward-rolling delete action D j Πz was performed is equal
to the key next to z in the database at the time D j Πz is performed, that is, y.But
then, by rule (3), T j would hold a commit-duration X lock on y at some timepoint