Information Technology Reference
In-Depth Information
Moreover, the two histories in case (1), as well as those in case (4), can be regarded
as “equivalent” because in each case T
1
is the same transaction reading the same set
of tuples.
t
In a serial history, all the transactions are executed one by one from the beginning
(action B)totheend(actionC ). Such a history must be viewed as correct, as long
as we do not impose any constraint on the timepoint when a transaction is expected
to be run or on the specific state of the logical database on which a transaction
is meant to be run. Recall from the discussion about the
ACID
property “
C
”in
Sect.
1.6
that the sequence of application-program steps that generates a transaction
is assumed to be correctly programmed for any serial execution. Indeed, when all
committed transactions are programmed to retain the consistency of an initially
consistent database, a serial history is guaranteed to retain the consistency of an
initially consistent database.
Two histories H and H
0
of the same transaction set
f
T
1
;:::;T
n
g
on database
D are
equivalent
if they produce on D the same database state. Observe that the
requirement that H and H
0
are histories of the same transaction set includes that
each transaction has exactly the same sequence of actions and with same input and
output both in H and in H
0
. Thus, in Example
5.2
, histories from two different cases
are not equivalent because transaction T
1
varies from one case to another.
There usually exist many nonserial histories that are equivalent to some serial
history, thus suggesting that transactions can be run concurrently in a nonserial way.
In classical concurrency control theory, a history that is equivalent to a serial history
is called
serializable
(a property that is weaker than the one with the same name to
be defined in Sect.
5.5
).
Example 5.3
One of the many possible nonserial histories of the transactions in
Example
5.1
is the history given for case (2). Using subscripting to distinguish
between actions belonging to different transactions, that history can be represented
alternatively as
B
1
R
1
Œ1; 1R
1
Œ2; 2R
1
Œ3; 3B
2
I
2
Œ4; 4C
2
R
1
Œ4; 4R
1
Œ
1
;0C
1
B
3
D
3
Œ2; 2C
3
,
where an action oŒ
N
x by transaction T
i
is denoted by o
i
Œ
N
x. Clearly, the history is
equivalent to the serial history for case (2) in Example
5.2
:
T
1
W
BR
Œ1; 1RŒ2; 2RŒ3; 3RŒ4; 4RŒ
1
;0C
T
2
W
BI
Œ4; 4C
T
3
W
BD
Œ2; 2C
Thus, the history is serializable in the classical sense. As will be seen soon, it is
also free of any isolation anomalies; hence it is acceptable.
t
In terms of the classical read-write transaction model, the
isolation
of transac-
tions means that a transaction T is not free to read or write data items written by
another transaction T
0
or to overwrite data items read by T
0
while T
0
is still active.
In our key-range transaction model, T is also not free to read a key range from
which T
0
has deleted a data item or to insert data items into a key range previously
read by T
0
.
