Information Technology Reference
In-Depth Information
Case (d) o
1
Œx
D
D
1
Œx and o
2
Œx
D
D
2
Œx.Thenx is in the database at H
0
,
T
1
holds a commit-duration X lock on y
D
x at H
0
,andT
2
should acquire a
short-duration X lock on x.
Thus, no dirty write can appear in H .
t
Lemma 6.13
Assume that a history
H
is permitted, on a given database, by the
rules (2)-(7) and the following relaxed version of the rule (1) of the key-range
locking protocol:
(1') For the read action
RŒx;
z
;
v
, a short-duration S lock is acquired on the key
x
of the tuple
.x;
v
/
to be read.
Then
H
contains no dirty reads.
Proof
For the sake of contradiction, assume that H contains a dirty read. By
Lemma
5.14
, we can write H as
H
D
˛o
1
ŒyLJR
2
Œx;
z
D
H
0
R
2
Œx;
z
,
where x
y
z
, o
1
Œy is a forward-rolling insert action I
1
Œy or delete action D
1
Œy
by some transaction T
1
active at H
0
, R
2
Œx;
z
;
v
is a read action by some transaction
T
2
other than T
1
, and the action sequence LJ does not contain the corresponding undo
action for o
1
Œy.
By Lemma
6.11
, T
1
holds a commit-duration X lock on the least key y
0
y in
the database at H
0
.Ifo
1
Œy is an insert action I
1
Œy, T
1
also holds a commit-duration
Xlockony at H
0
, by rule (2). Because of the S lock acquired by T
2
on x, y
6D
x.
Thus x>y
z
and y cannot be in the database at H
0
. Since, by the definition of
the read action R
2
Œx;
z
, x is the least key in the database at H
0
with x
z
,we
conclude that x
D
y
0
, which however is not possible because of the X lock held on
y
0
by T
1
at H
0
.
We are left with the case that o
1
Œy is a delete action D
1
Œy.Ify is in the database
at H
0
, the condition x
y
z
and the fact that x is the least key with x
z
and
y
0
the least key
y in the database at H
0
imply that y
0
D
y
D
x, which however
is impossible because of the X lock held by T
1
on y
0
at H
0
and the S lock acquired
by T
2
on x. On the other hand, if y is not in the database at H
0
, we conclude that
y
0
D
x, which is also impossible for the same reasons.
t
In order to prove that unrepeatable reads are not permitted, we need to show that
the key-range locking protocol does not permit a history
T
1
:
:::
RŒx;
z
:::
T
2
:
:::
oŒy
:::
where oŒy is a forward-rolling insert or delete action, x
y
z
,andT
1
has not
committed or performed a partial rollback or initialized a total rollback that includes
RŒx;
z
at the time T
2
performs the action oŒy. Here we cannot conclude that in
the case x>y,thekeyx would be the key next to y, because after performing
RŒx;
z
transaction T
1
may have performed actions that have changed the key next
to
z
. However, we have:
