Information Technology Reference
In-Depth Information
Example 12.2 Assume that the transaction-time database contains initially the
versioned tuples .1; T 0 ; u 0 / and .4; T 0 ; v 0 /. Consider different interpretations of the
following history of two update transactions:
RŒy; > 2; w 0 C
T 1 :
BI Œ2; w 1 RŒx; > 1; w
T 2 : BI Œ3; w 2 C
As it is natural that transactions see their own updates, the read action RŒx; >1; w
must retrieve the tuple .2; w 1 /. But should the read action RŒy; >2; w 0 retrieve the
tuple .3; w 3 /, whose key is the least key greater than 2 in the most recent committed
database version ( commit-time .T 2 /), or the tuple .4; v 0 /, whose key is the least key
greater than 2 in the database of version start-time .T 1 /? In the latter case, the history
is equivalent to the serial history
T 1 : BI Œ2; w 1 RŒ2; > 1; w 1 RŒ4; > 2; v 0 C
T 2 : BI Œ3; w 2 C
where the commit order of the transactions is reversed. In the former case, the
history is equivalent to the reversed serial history
T 1 :
BI Œ2; w 1 RŒ2; > 1; w 1 RŒ3; > 2; w 2 C
T 2 : BI Œ3; w 2 C
that respects the original commit order. Note that in this case start-time .T 1 /
commit-time .T 2 /,sothatT 1 must also see the update of T 2 .
t
Obviously, read actions by an update transaction that read anything other than
the most recent data are unrepeatable and can cause the integrity of the database to
be lost, as shown in the examples given in Sect. 5.4 .
An update action, that is, a write action WŒx; u ; v , an insert action IŒx; v ,or
a delete action DŒx; v , is always based on the most recent committed database
version, that is, version ,where is the greatest timestamp in the commit-time table
at the time the action is executed. Moreover, no update actions by other transactions
on key x must be ongoing at the same time. This is necessary to maintain the
constraint that only linear version histories are allowed.
Accordingly, to perform a write action WŒx; u ; v in update transaction T ,ifthis
is the first update by T on key x, the tuple .x; u / with key x in the most recent
committed database version is retrieved, the versioned tuple .x; T; v / is inserted into
the database, and the insertion is redo-undo logged in the usual way. In this case the
most recent committed database version must contain a versioned tuple .x; T 0 ; v 0 /
with v 0 6D? .Otherwise,ifT has earlier inserted or written the tuple with key x,
so that a versioned tuple .x; T; u / exists, then that tuple is replaced by the tuple
.x; T; v /, and the replacement is redo-undo logged.
To perform an insert action IŒx; v , if this is the first update on key x by T ,the
versioned tuple .x; T; v / is inserted into the database, and the insertion is redo-undo
logged. In this case the most recent committed database version must not contain
any tuple with key x other than one of the form .x; T 0 ; ? /.Otherwise,ifT has
earlier deleted the tuple, so that a versioned tuple .x; T; ? / exists, then that tuple is
replaced by the tuple .x; T; v / and the replacement is redo-undo logged.
Search WWH ::




Custom Search