Information Technology Reference
In-Depth Information
where o
0
1
Œx is a forward-rolling update action for which there is no corresponding
undo action in LJ
0
.
Now if o
2
Œx is an undo action, we can further write H either as
H
D
˛
0
o
0
1
ŒxLJ
00
o
0
2
ŒxLJ
2
o
2
Œx
D
˛
0
o
0
1
ŒxLJ
00
o
0
2
Œx
0
or as
H
D
˛
00
o
0
2
ŒxLJ
00
o
0
1
ŒxLJ
0
o
2
Œx
D
˛
00
o
0
2
ŒxLJ
00
o
0
1
Œx
0
,
depending on whether the forward-rolling action o
0
2
Œx corresponding to the undo
action o
2
Œx is in LJ
0
or in ˛
0
. In the former case the undo action for o
0
1
Œx,ifany,
is not in LJ
00
, since it is not in LJ
0
D
LJ
00
o
0
2
ŒxLJ
2
. In the latter case T
2
is active at
˛
00
o
0
2
ŒxLJ
00
and the undo action o
2
Œx for o
0
2
Œx is not in LJ
00
, since it is in
0
. Thus
both of these cases exhibit the required form of the history H .
t
The appearance of dirty reads in a history can always be characterized by a
conflicting pair of a forward-rolling update action and a read action:
Lemma 5.14
Let
H
be a history of transactions in the read-write or key-range
transaction model. If
H
contains a dirty read, then
H
is of the form
H
D
˛o
1
ŒyLJR
2
Œx;
z
,
where
x
y
z,
o
1
Œy
is a forward-rolling insert action
I
1
Œy
, delete action
D
1
Œy
,
or write action
W
1
Œy
by some transaction
T
1
active at
˛o
1
ŒyLJ
,
R
2
Œx;
z
is a read
action by some transaction
T
2
other than
T
1
, and the action sequence
LJ
does not
contain the undo action for
o
1
Œy
.
Proof
By the definitions of a dirty read and an uncommitted update, we can write
H as
H
D
˛o
1
ŒyLJR
2
Œx;
z
,
where x
y
z
, the action o
1
Œy by transaction T
1
is the last update on key y
in ˛o
1
ŒyLJ, T
1
is active at ˛o
1
ŒyLJ, the action R
2
Œx;
z
is a read action by some
transaction T
2
other than T
1
, and, if o
1
Œy is an undo action, then it does not restore
y to its committed state, so that there is in ˛ a forward-rolling update action o
0
1
Œy
on y by T
1
that has no corresponding undo action in ˛o
1
ŒyLJ.
Thus, if o
1
Œy is an undo action, we can write H as
H
D
˛
0
o
0
1
Œy˛
2
o
1
ŒyLJR
2
Œx;
z
D
˛
0
o
0
1
ŒyLJ
0
R
2
Œx;
z
,
where o
0
1
Œy is a forward-rolling update action for which there is no corresponding
undo action in LJ
0
, as required.
t
A history that contains an unrepeatable read but no dirty reads can be character-
ized by a conflicting pair of a read action and a forward-rolling update action:
Lemma 5.15
Let
H
be a history of transactions in the read-write or key-range
transaction model. If
H
contains an unrepeatable read, then
H
either contains a
dirtyreadorisoftheform
H
D
˛R
1
Œx;
z
LJo
2
Œy
,
