Information Technology Reference
In-Depth Information
8.8
Consider executing the transaction
BR
Œx
1
;>9;
v
1
RŒx
2
;>x
1
;
v
2
RŒx
3
;>x
2
;
v
3
RŒx
4
;>x
3
;
v
4
C
on the database indexed by the B-link tree of Fig.
8.13
. Assuming that the saved
path has its initial value set by the call
initialize-saved-path
./ and that no other
transactions are in progress simultaneously, what page latchings and unlatchings of
B-link tree pages occur during the execution of the transaction?
8.9
Give algorithms for redo-only structure modifications for B-link trees. Each
modification should only modify a single level of the tree and retain the (relaxed)
consistency defined for B-link trees, so that each child page of each page of the tree
is accessible, if not directly via a parent-to-child link, via a parent-to-child link to
the eldest child and the sideways link chain. How are these modifications used in
the execution of the following transaction on the B-link tree of Fig
8.13
?
BI Œ18I Œ20I Œ21DŒ1DŒ3C .
8.10
Thanks to the relaxed balance conditions of the B-link tree, there exists a
very simple method to load the contents of a file f into an initially empty relation
r implemented as a B-link tree. In the spirit of the load process suggested for B-
trees in Sect.
8.8
, outline an algorithm for loading a B-link tree and for repairing its
imbalance from which it may initially suffer.
8.11
Along the lines discussed in Sect.
8.8
, outline a restartable algorithm for
loading a B-tree. For triggering the page splits and tree-height increases needed,
use the procedure
find-page-for-insert
.p; p
0
;x;
v
;y/ simplified so that the page p
0
and the next key y
0
are not determined. We also assume that the procedures
page-
split
.p;q;x
0
;q
0
/ and
tree-height-increase
.p;q;x
0
;q
0
/ are changed so that they
move to page q
0
only two records.
Bibliographical Notes
Traditional B-tree algorithms perform structure modifications bottom-up along the
insertion or deletion path, as described in many textbooks on database management.
In many early studies on B-tree concurrency control, transactional access and
recovery issues are either omitted or discussed very briefly. Biliris [
1987
] makes the
important observation that the commit of a structure modification is independent
of the commit of the transaction that triggered the modification, so that a structure
modification (that retains the consistency of the B-tree) can be allowed to commit
even though the triggering transaction eventually aborts and rolls back. Fu and
Kameda [
1989
] consider concurrent access to B-trees in the context of nested multi-
action transactions.
Mohan [
1990a
,
1996a
], Mohan and Levine [
1992
], and Lomet and Salzberg
[
1992
,
1997
] were the first to publish detailed algorithms for managing transactions
on database relations indexed by B-trees, compatible with the
ARIES
recovery
