Information Technology Reference
In-Depth Information
identifier of the transaction, which is then, if the transaction does commit, mapped
to a
commit timestamp
that reflects the time when the transaction committed.
Thus, instead of tuples .x;
v
/ of a single-version relation r.X;V/,ina
transaction-time relation of the same schema, we have
versioned tuples
of the
form .x; T;
v
/,whereT is the transaction identifier of the transaction that created
the tuple. Here the pair .x; T / forms a unique key of the versioned tuple among all
versioned tuples.
When a transaction T
0
updates a tuple with key x for the first time in the
transaction, it is given the most recent versioned tuple .x; T;
v
/, if one exists. This
tuple must be committed, before T
0
can update it. The first update by T
0
on the tuple
creates a new versioned tuple .x; T
0
;
v
0
/. Any further updates by T
0
on x occur “in
place,” that is, they just change the value component
v
0
of the tuple. If T
0
commits, it
leaves behind the newest version of the tuple containing the last update by T
0
on it.
Otherwise, if T
0
does not commit but aborts and rolls back, no new version created
by T
0
is left behind.
The deletion by T
0
of a tuple with key x is represented by the new versioned
tuple .x; T
0
;
?
/. The insertion by T
0
of a tuple .x;
v
0
/ is legal only if there is not yet
any versioned tuple with key x or if the most recent versioned tuple with key x is
.x; T;
?
/.
The above rules mean that we only allow
linear version histories
:foranykeyx,
the versioned tuples with key x form a sequence
.x; T
1
;
v
1
/; .x; T
2
;
v
2
/;:::;.x;T
n
;
v
n
/;
where the transactions have committed in the order T
1
;T
2
;:::;T
n
and, for all i
D
2;:::;n, transaction T
i
has only seen version .x;
v
i1
/ of the tuple with key x when
creating version .x;
v
i
/.
The mapping from transaction identifiers to commit timestamps is maintained in
a relation of schema
commit-time
.
transaction-id
;
timestamp
/,
called the
commit-time table
. This table is organized as a sparse B-tree index with
transaction identifiers as keys. Concurrent operations on the table are controlled by
a single
tree latch
on the B-tree, so that only one transaction at a time is allowed to
insert to the table.
When transaction T is about to commit, it write-latches the commit-time table,
reads the system clock, creates a new timestamp , inserts the tuple .T; / into the
commit-time table, logs the insertion with a redo-undo log record in the normal
way, unlatches the table, and then commits, that is, performs the normal commit
processing. This procedure ensures that the commit timestamps are unique and
respect the true chronological commit order, that is, the order of the commit log
records in the log.
As insertions into the commit-time table are logged with usual redo-undo log
records, if it happens that T , after inserting into it, does not commit after all, then
