Information Technology Reference
In-Depth Information
Lemma 6.14
Assume that the history
H
D
˛R
1
Œy;
z
LJ
is permitted by the key-range locking protocol on a given database, and transaction
T
1
is active and has not performed a partial rollback or initialized a total rollback
that includes the action
R
1
Œy;
z
.Then
T
1
holds commit-duration locks on all keys
y
00
with
y
0
y
00
z in the database at the end of the history, where
y
0
is the least
key with
y
0
y
in that database.
Proof
As in the proof of Lemma
6.11
, we consider the history
H
0
D
˛R
1
Œy;
z
LJ
0
,
where the action sequence LJ
0
is LJ stripped off all actions by T
1
involved in partial
rollbacks. We use induction on the number of insert, delete, undo-insert, and undo-
delete actions in LJ
0
.
In the base case, there are no such actions in LJ
0
. Thus y
0
D
y is the least key with
y
0
y and y
00
D
y the only key with y
0
y
00
z
in the database at ˛R
1
Œy;
z
as
well as in the database at ˛R
1
Œy;
z
LJ
0
and hence in the database at H . By rule (1)
of the key-range locking protocol, the key y is S-locked by T
1
for commit duration.
This proves the base case.
In the induction step, we assume that LJ
0
contains n>0insert, delete, undo-
insert, or undo-delete actions and that the lemma holds for the longest prefix LJ
1
of
LJ
0
that does not include the last action, o
2
Œy
00
, of interest. Then H
0
can be written
as
H
0
D
˛R
1
Œy;
z
LJ
0
D
˛R
1
Œy;
z
LJ
1
o
2
Œy
00
LJ
2
.
As an induction hypothesis, we assume that T
1
holds commit-duration locks on all
keys y
00
with y
0
y
00
z
in the database at ˛R
1
Œy;
z
LJ
1
where y
0
is the least key
y in that database.
Because of the commit-duration locks held by T
1
on all keys y
00
with y
0
y
00
z
in the database at ˛R
1
Œy;
z
LJ
1
, the action o
2
Œy
00
cannot be an insert action I
2
Œy
00
or
a delete action D
2
Œy
00
or an undo-insert action I
2
Œy
00
, by any transaction T
2
other
than T
1
,ify
0
y
00
z
. Note that, by rules (2) and (3), such a transaction T
2
should
hold a commit-duration X lock on y
00
for I
2
Œy
00
or for I
2
Œy
00
, or a short-duration
Xlockony
00
for D
2
Œy
00
. Also, if o
2
Œy
00
were an undo-delete action D
2
Œy
00
, then,
by Lemma
6.10
,thekeynexttoy
00
would be the same as in the database at the time
the corresponding forward-rolling action D
2
Œy
00
was performed and T
2
would hold
a commit-duration X lock on that next key at ˛R
1
Œy;
z
LJ
1
. However, this is not
possible with y
0
y
00
z
. Note that y
00
cannot be y
0
(locked by T
1
); hence y
00
<y
0
and the key next to y
00
is among those locked for commit duration by T
1
. Thus we
conclude that o
2
Œy
00
, with y
0
y
00
z
, can only be an action by T
1
itself.
As LJ
0
contains no undo actions by T
1
, the action o
2
Œy
00
with y
0
y
00
z
can
only be an insert action IŒy
00
or a delete action DŒy
00
by T
1
. In the case of an insert
action IŒy
00
, T
1
holds a commit-duration X lock on y
00
, by rule (2), as desired. The
case of a delete action DŒy
00
is interesting only in the case y
00
is the least key
y
in the database at ˛R
1
Œy;
z
LJ
1
. Then the key y
0
next to the deleted key is required
