Transactional Isolation - Transaction Processing - page 107

In the definition of unrepeatable reads, it should be noted that a read action
R 1 Œx; z is not regarded as unrepeatable in the history
˛R 1 Œx; z LJo 2 Œy
if T 1 is backward-rolling at ˛R 1 Œx; z LJ. This is because T 1 will eventually roll back
all its updates, including those possibly based on the unrepeatably read key.
The update actions exhibiting one of the three isolation anomalies defined above
can be forward-rolling insert, delete, or write actions or undo actions. However, if
such an action is an undo action, the anomaly may also be exhibited by a forward-
rolling action.

Example 5.12 In the history
B 1 :::W 1
1

Œx:::B 2 :::W 1
2

Œx:::C 2 :::C 1

the action W 1
2

dirty write, if W 1

1 Œx is the last update on x in
B 1 :::W 1 Œx:::B 2 ::: and does not restore x to its original, committed state.
But then the history must be of the form
B 1 :::o 1 Œx:::W 1 Œx:::W 1 Œx:::B 2 :::W 2 Œx:::W 2 Œx:::C 2 :::C 1 ,
where W 1 Œx and W 2 Œx are the forward-rolling actions that are undone by the
actions W 1 Œx and W 2 Œx, respectively, and o 1 Œx is a forward-rolling update
action on x. The pair of forward-rolling update actions o 1 Œx and W 2 Œx now exhibit
a dirty write.

Œx is a

t

The following lemma states that the appearance of dirty writes in a history can
always be characterized by a pair of conflicting forward-rolling update actions.

Lemma 5.13 Let H be a history of transactions in the read-write or key-range
transaction model. If H contains a dirty write, then H is of the form

H D ˛o 1 ŒxLJo 2 Œx ,
where o 1 Œx is a forward-rolling insert action I 1 Œx , delete action D 1 Œx , or write
action W 1 Œx by some transaction T 1 active at ˛o 1 ŒxLJ ; o 2 Œx is a forward-rolling
insert action I 2 Œx , delete action D 2 Œx or write action W 2 Œx by some transaction T 2
other than T 1 ; and the action sequence LJ does not contain the undo action for o 1 Œx .
Proof By the definitions of a dirty write and an uncommitted update, we can write
H as

H D ˛o 1 ŒxLJo 2 Œx ,
where the action o 1 Œx by transaction T 1 is the last update on key x in ˛o 1 ŒxLJ, T 1
is active at ˛o 1 ŒxLJ, the action o 2 Œx is an update on x by some transaction T 2 other
than T 1 , and, if o 1 Œx is an undo action, then it does not restore x to its committed
state, so that there is in ˛ a forward-rolling update action o 0 1 Œx on x by T 1 that has
no corresponding undo action in ˛o 1 ŒxLJ.
Thus, if o 1 Œx is an undo action, we can write H as
H D ˛ 0 o 0 1 Œx˛ 2 o 1 ŒxLJo 2 Œx D ˛ 0 o 0 1 ŒxLJ 0 o 2 Œx ,