Information Technology Reference
In-Depth Information
(Recall the formal definition of a transaction as a pair of a transaction identifier and
a transaction state.)
Case (1) occurs in interleavings in which the action IŒ4;4 of T
2
is executed
after the action RŒ
1
;0 of T
1
and the action DŒ2; 2 of T
3
is executed after the
action RŒx
2
;>1;
u
2
of T
1
, such as in the following interleaving:
T
1
W
BR
Œ1; 1RŒ2; 2RŒ3; 3RŒ
1
;0C
T
2
W
BI
Œ4; 4C
T
3
W
BD
Œ2; 2C
Case (2) occurs when IŒ4;4 is executed before RŒx
4
;> 3;
u
4
,butDŒ2; 2 is
executed after RŒx
2
;>1;
u
2
, such as in the following:
T
1
W
BR
Œ1; 1RŒ2; 2RŒ3; 3
RŒ4; 4RŒ
1
;0C
T
2
W
BI
Œ4; 4C
T
3
W
BD
Œ2; 2C
Case (3) occurs when IŒ4;4 is executed after RŒ
1
;0,butDŒ2; 2 is executed
before RŒx
2
;>1;
u
2
. Case (4) occurs when IŒ4;4 is executed before RŒx
4
;>3;
u
4
and DŒ2; 2 is executed before RŒx
2
;>2;
u
2
.
t
Let
f
T
1
;:::;T
n
g
be a set of transactions. This set can contain forward-rolling,
committed, backward-rolling, and rolled-back transactions. A
transaction schedule
or
transaction history
H of the set of transactions
f
T
1
;:::;T
n
g
is a
shuffle
of the
action strings T
1
;:::;T
n
.Inotherwords,H is an action sequence that satisfies the
following conditions:
1. H is an action sequence composed exactly of the actions present in the
transactions T
1
;:::;T
n
.
2. The actions of each transaction T
i
are present in H in the same order as in T
i
,
that is, H is of the form ˛
1
LJ
1
˛
2
LJ
2
:::LJ
m
˛
mC1
,whereLJ
1
LJ
2
:::LJ
m
D
T
i
.
A
serial history
H is a permutation of entire transactions of which at most
one, the last, is active. In a serial history all the actions of each transaction T
i
are
consecutive, so that H is of the form T
i
1
:::T
i
n
,where
f
i
1
;:::;i
n
gDf
1;:::;n
g
,
and each transaction T
i
j
, j
D
1;:::;n
1, is committed or rolled back. A history
that is not serial is called a
nonserial history
.
Example 5.2
For the transactions of Example
5.1
, the possible serial histories are
in the four cases:
1. T
1
T
2
T
3
or T
1
T
3
T
2
.
2. T
2
T
1
T
3
.
3. T
3
T
1
T
2
.
4. T
2
T
3
T
1
or T
3
T
2
T
1
.
All the six histories result in the same database:
f
.0; 0/; .1; 1/; .3; 3/; .4; 4/
g
.