Information Technology Reference
In-Depth Information
Example 5.5
Consider the following history for a rolled-back transaction T
1
:
H
D
BI
Œy;
w
DŒx;
u
I Œx;
v
AI
1
Œx;
v
D
1
Œx;
u
I
1
Œy;
w
C .
Key y has an uncommitted update by T
1
in the following prefix of H :
BI
Œy;
w
.
In the following prefixes of H ,keysy and x have uncommitted updates by T
1
:
BI
Œy;
w
DŒx;
u
.
BI
Œy;
w
DŒx;
u
I Œx;
v
.
BI
Œy;
w
DŒx;
u
I Œx;
v
A.
BI
Œy;
w
DŒx;
u
I Œx;
v
AI
1
Œx;
v
.
Key y has an uncommitted update by T
1
in the prefix
BI
Œy;
w
DŒx;
u
I Œx;
v
AI
1
Œx;
v
D
1
Œx;
u
.
However, x is already committed here, because the last update on x is by the undo
action D
1
Œx;
u
, and the corresponding forward-rolling action DŒx;
u
is the first
update on x by T
1
.Bothx and y are committed in the prefix
H
D
BI
Œy;
w
DŒx;
u
I Œx;
v
AI
1
Œx;
v
D
1
Œx;
u
I
1
Œy;
w
,
although the transaction is still active, namely, backward-rolling, because its
rollback has not yet been completed with the commit action C . Of course, the
transaction is de facto rolled back, because C is the only action it can (and must) do
next.
t
By the above definition, a partial rollback of a forward-rolling transaction can
change an uncommitted key x to committed, after which the transaction can again
update x, after which a new partial rollback can change x to committed.
Example 5.6
In the following, as the history advances, the key x changes from
uncommitted to committed, then to uncommitted, then to committed, then to
uncommitted, and finally to committed.
BS
ŒP W Œx.
BS
ŒP W ŒxAŒP W
1
Œx.
BS
ŒP W ŒxAŒP W
1
ŒxC ŒP S ŒQW Œx.
BS
ŒP W ŒxAŒP W
1
ŒxC ŒP S ŒQW ŒxAŒQW
1
Œx.
BS
ŒP W ŒxAŒP W
1
ŒxC ŒP S ŒQW ŒxAŒQW
1
ŒxC ŒQW Œx.
BS
ŒP W ŒxAŒP W
1
ŒxC ŒP S ŒQW ŒxAŒQW
1
ŒxC ŒQW ŒxC .
t
5.3
Isolation Anomalies
In a concurrent history, the isolation of transactions can be violated in several ways.
The isolation violations can be classified into three
isolation anomalies
: dirty writes,