Information Technology Reference
In-Depth Information
2. o
1
Œx updates key x and o
2
Œy reads a key range that contains x. This situation is
called a
write-read conflict
.
3. o
1
Œx reads a key range and o
2
Œy updates a key y that belongs to the range read
by o
1
Œx. This situation is called a
read-write conflict
.
Transactions T
1
and T
2
conflict
in H , denoted T
1
<T
2
,ifo
1
Œx < o
2
Œy in H for
some pair of actions o
1
Œx of T
1
and o
2
Œy of T
2
.
Example 5.26
Consider the transactions T
1
D
BR
Œx;
xRŒy;
y and T
2
D
BR
Œx;
xIŒyC (where x
6D
y) and their nonserial history
H
1
D
T
1
W
BR
Œx;
x
RŒy;
y
T
2
W
BR
Œx;
xIŒyC
There is only one conflict here, namely, the write-read conflict caused by the pair
of actions I
2
Œy and R
1
Œy;
y. This means that T
2
<T
1
. The same conflict is also
present in the following serial history of the same transactions:
H
2
D
T
1
W
BR
Œx;
xRŒy;
y
T
2
W
BR
Œx;
xIŒyC
That is, all of T
2
is performed first, followed by all of T
1
. Obviously, H
1
and H
2
are
equivalent.
t
Now assume that for all pairs of different transactions T
1
and T
2
in a history H
the following condition holds:
If T
1
<T
2
then T
2
6
<T
1
.
In other words, the conflict relationship “<” between transactions of H is antisym-
metric (and thus the corresponding reflexive relationship “
”
D
“<”
[
“
D
”isa
partial order). If in addition at most one transaction in H is active and T<T
0
does
not hold for the active transaction T and any other transaction T
0
of H ,thenwe
say that H is
conflict-serializable
and that the partial order “<”isthe
serializability
order
of the transactions of H .
Theorem 5.27
A conflict-serializable history is equivalent to any serial history of
the same transactions in which the transactions appear in an order that respects the
conflict relationship “
<
.”
Proof
Two histories H
1
and H
2
are clearly equivalent if H
1
can be transformed
into H
2
by a series of swaps of two non-conflicting consecutive actions. This
implies that a conflict-serializable history with respect to “<” can be transformed
into an equivalent serial history where the transactions are ordered with respect
to “<.”
t
Example 5.28
For the transactions in the history H
1
of Example
5.26
, T
2
<T
1
holds but T
1
<T
2
does not. Also, only T
1
is active. Thus, the history is conflict-
serializable. In the serial history H
2
equivalent to H
1
the transactions appear in the
order T
2
T
1
, respecting the serializability order.
t
