Lock-Based Concurrency Control - Transaction Processing - page 138

between D i Œx and D i Œx, which is impossible because of the X lock on y held by
T i . Thus y 0 D y, as claimed. t
Lemma 6.10 implies that when performing an undo-delete action D 1 Œx,the
transaction holds a commit-duration X lock on the current next key y of the deleted
key x.

Lemma 6.11 Assume that the history

H D ˛o 1 ŒxLJ
is permitted by the rules (2) to (7) of the key-range locking protocol on a given
database, transaction T 1 is active at H , o 1 Œx is either an insert action IŒx or a
delete action DŒx , and the action sequence LJ does not contain the undo action
for o 1 Œx .Then T 1 holds a commit-duration X lock on the least key y x in the
database at the end of the history.

Proof First we note that if the action sequence LJ contains some undo actions by T 1 ,
then the corresponding forward-rolling actions must also be included in LJ, because
otherwise also the action o 1 Œx would be undone in LJ, contradicting the assumption.
Let LJ 0 be the sequence LJ stripped off all actions involved in partial rollbacks by T 1 .
The history H 0 D ˛o 1 ŒxLJ 0 then produces exactly the same database as H . Because
by rule (6), upon completing a partial rollback to a savepoint, exactly those locks
are released that were acquired after setting the savepoint, the set of locks held by
T 1 at H 0 is the same as at H .
The proof of the lemma is now by induction on the number of actions in LJ 0 that
change the least key x in the database at ˛o 1 Œx through ˛o 1 ŒxLJ 0 .
In the base case, there are no actions in LJ 0 that change the least key x in the
database. Thus, the least key y x in the database at ˛o 1 ŒxLJ 0 is the same as that
in the database at ˛o 1 Œx.Ifo 1 Œx is an insert action IŒx, y D x and T 1 holds a
commit-duration X lock on x, by rule (2). If o 1 Œx is a delete action DŒx, y is the
key next to x and T 1 holds a commit-duration X lock on y, by rule (3). This proves
the base case.
For the induction step, we assume that LJ 0 contains n>0actions that change the
least key x in the database and assume that the lemma holds for prefixes of LJ 0
that contain n 1 such actions. Let o 2 Œy 0 be the last such action in LJ 0 .ThenLJ 0 can
be written as LJ 1 o 2 Œy 0 LJ 2 , where the least key x remains the same through LJ 2 .As
an induction hypothesis, we assume that T 1 holds a commit-duration X lock on the
least key y x in the database at ˛o 1 ŒxLJ 1 .WehavetoprovethatT 1 also holds
such a lock at
H 0 D ˛o 1 ŒxLJ 1 o 2 Œy 0 LJ 2 D ˛o 1 ŒxLJ 0 .
Because of the commit-duration X lock held by T 1 on the least key y x in
the database at ˛o 1 ŒxLJ 1 , the action o 2 Œy 0 that changes this situation cannot be an
insert action I 2 Œy 0 with y>y 0 x or a delete action D 2 Œy or an undo-insert
action I 2 Œy, by any transaction T 2 other than T 1 . Note that, by rules (2) and (3),
such a transaction T 2 would have to hold a short-duration X lock on the key y next