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 .
Search WWH ::




Custom Search