Information Technology Reference
In-Depth Information
12.7
Version Management with B-Trees
The basic sparse B-tree index discussed in Chaps.
7
and
8
offers as such a
simple, although not the most efficient, physical database structure for managing
a transaction-time database. We just regard versioned tuples .x; T;
v
/ of a logical
database r.
X
;V/ as tuples in a relation r.
X
;
T
;V/, where the ordered pair XT is
the key of the relation. We call such a B-tree a
versioned B-tree
.
In the leaf pages of the versioned B-tree for r , the different versions
.x; T
1
;
v
1
/; .x; T
2
;
v
2
/;:::;.x;T
n
;
v
n
/
of the tuple with key x are stored side by side, ordered by the transaction identifiers,
so that the first versioned tuple .x; T
1
;
v
1
/, that is, the one with the least transaction
identifier T
1
, resides in the leaf page covering key .x; T
1
/, and the last versioned
tuple .x; T
n
;
v
n
/, that is, the one with the greatest transaction identifier T
n
, resides
in the leaf page covering key .x; T
n
/.
Assume now that transaction T wants to execute a read action RŒx;
z
;
v
on the
database of version ,where is some timestamp greater than or equal to
start-
time
.T / and less than or equal to the start time of the action RŒx;
z
;
v
. Such reads
appear in read-only transactions running at transaction-level read consistency and in
all transactions at statement-level read consistency and snapshot isolation.
We must determine the least key x with x
z
among the keys x present at time
or inserted or written by T itself. To that end, we scan keys x in ascending order
starting at the least key x with x
z
until we find one that is present at time or has
been inserted or written by T .
First, a procedure call
find-pages-for-read
.P;
z
/ is used to locate and read-latch
the set P of leaf pages that contain the versioned tuples with the least key x with
x
z
. The commit-time table is read-latched, the set of records for the transactions
that created the versioned tuples with key x is retrieved from the commit-time table,
and the commit-time table is unlatched. Among the versioned tuples .x; T
0
;
v
0
/ with
commit-time
.T
0
/
, if such tuples exist, the one with the greatest commit time is
determined. Also the tuple .x; T;
v
/ created by T , if one exists, is determined.
We have to consider the following cases (of which only cases 3, 4, and 5 can
appear in a read-only transaction):
1. .x; T;
v
/ exists and
v
6D?
.ThenT itself has inserted or written a tuple with key
x; the tuple .x;
v
/ is returned.
2. .x; T;
v
/ exists and
v
D?
.ThenT itself has deleted the tuple with key x;we
move to the key next to x.
3. .x; T;
v
/ does not exist but .x; T
0
;
v
0
/ with
v
0
6D?
exists. The tuple .x;
v
0
/ is
returned.
4. .x; T;
v
/ does not exist but .x; T
0
;
v
0
/ with
v
0
D?
exists. Then we move to the
key next to x.
5. Neither .x; T;
v
/ nor .x; T
0
;
v
0
/ exists. The tuple .
1
;0/is returned.
