Transactional Isolation - Transaction Processing - page 116

be run. In one such , the undo actions are in reverse chronological order of the
corresponding forward-rolling actions of the active transactions.

Proof By Theorem 4.8 , the theorem holds true if the string is chosen as the action
sequence implied by the undo pass of the recovery algorithm presented in Chap. 4 .
Then, because in H no dirty writes have been executed, for each undo action in
the database must contain the result of the corresponding forward-rolling action; so
it is possible to undo that action. The undo actions performed in the undo pass are
in reverse chronological order of the update actions in H . t

Theorems 5.24 and 4.8 imply that the undo pass of ARIES recovery is possible if
all transactions are run at isolation level 1 ı or higher.
It makes sense to require that multiple transactions can roll back during normal
transaction processing and that this can happen concurrently in any order. Thus,
dirty writes must be completely prevented. The database management system must
not produce any histories where a transaction would perform dirty writes. It is not
feasible in practice to prevent the dirty writes of just the committed and rolled-back
transactions.
In the literature, a strict history is one in which no committed or rolled-back
transaction does dirty writes and, additionally, no transaction performs dirty reads.

Theorem 5.25 Let H be a history in which no transactions do dirty writes. Let
be any interleaving of the action sequences used to complete the active transactions
in H to rolled-back transactions. Then we have:

1. The completed history H can be run on any database on which H can be run.
2. None of the transactions in H do dirty writes.
3. None of the transactions in H do dirty reads, unless one of the transactions in
H does a dirty read.
4. None of the transactions in H do dirty or unrepeatable reads, unless one of the
transactions in H does a dirty or an unrepeatable read.

Proof We leave the proving of this theorem as an exercise. t

5.7 Conflict-Serializability

We say that action RŒx; z reads key range Œ z ;x, action RŒx; > z reads key range
. z ;x, and actions IŒx, DŒx,andWŒx update key x. The read action RŒx of
the read-write model does the same thing as the key-range-model action RŒx; x.
Thus, the action reads the key x.
Let H be a history that contains no partial rollbacks, let T 1 and T 2 be two
different transactions in history H ,andleto 1 Œx and o 2 Œy be actions by T 1 and
T 2 , respectively, such that o 1 Œx precedes o 2 Œy in H . We define that o 1 Œx conflicts
with o 2 Œy in H , denoted o 1 Œx < o 2 Œy, if one of the following conditions holds:
1. x D y and o 1 Œx and o 2 Œy both update key x. This situation is called a write-
write conflict .