Information Technology Reference
In-Depth Information
Theorem 5.29
Let
H
be a history of transactions in which at most one is forward-
rolling and the other are committed and in which no transaction contains partial
rollbacks. If
H
does not contain any isolation anomalies (dirty writes, dirty reads,
or unrepeatable reads), then it is conflict-serializable.
Proof
Assume the contrary, that is, H is not conflict-serializable. Then there is a
sequence of transactions T
1
;T
2
;:::;T
n
, n
2, that appear in H such that
T
1
<T
2
;T
2
<T
3
;:::; T
n
<T
1
:
Without loss of generality we may assume that T
1
is committed. This means that H
is of the form
o
1
Œx
0
T
1
W
:::
o
1
Œx
:::
:::
T
2
W
:::
o
2
Œy
:::
H
D
:
T
n
W
::: o
n
Œy
0
:::
where o
1
Œx and o
2
Œy,aswellaso
n
Œy
0
and o
1
Œx
0
are pairs of conflicting actions.
Because the commit action of T
1
cannot appear before o
2
Œy, H contains an isolation
anomaly.
t
The converse of Theorem
5.29
does not hold.
Example 5.30
The history
T
1
W
BW
Œx
C
T
2
W
BW
Œx
C
of two committed transactions T
1
and T
2
is conflict-serializable, with T
1
T
2
as the
serializability order, but the write action of T
2
is a dirty write.
t
Also recall that the isolation anomalies were defined for general histories that
can contain any number of active transactions, besides committed and rolled-back
transactions, and that transactions may contain partial rollbacks (which we excluded
above when defining conflicts). Obviously, in order to be able to state a meaningful
converse of Theorem
5.29
, we would have to refine and extend the definition of
conflicting actions, so as to observe the commit action C and the undo actions
contained in partial and total rollbacks. For the purposes of the approach taken in this
topic to concurrency control, it is not necessary to elaborate that issue any further.
5.8
Enforcing Isolation
As was stated earlier, it must be possible to program transactions without having to
care about other concurrent transactions. The programmer of a database application
needs only to ensure that each transaction preserves the consistency of the logical
