Information Technology Reference
In-Depth Information
leaf page with the next not-yet-inserted tuples, advancing the cursor
z
to the key of
the last tuple inserted into the page, and causing a split at the next attempt to insert
more of the remaining tuples into a full leaf page.
If the load process succeeds to reach the end of the file f , it writes the log record
h
end-load
;r;f
i
:
(8.8)
To help tracing errors in the load process, the
start-load
and
end-load
log records
might also carry the timestamp and other descriptive information about the source
file f such as the number of tuples with keys greater than
z
,andthe
end-load
log record might carry aggregate information about the load such as the number
of inserted tuples.
To avoid the dependence of database durability on the file f , we can always log
the inserted tuples themselves, so that instead of the log record (
8.6
)weusethelog
record
h
populate-leaf-page
;p;V
i
;
(8.9)
where V is the set of tuples inserted into page p.
As the tuple insertions performed by the load process are all redo-only oper-
ations, the loading can be undone only by running a transaction that effectively
undoes the insertions. This can be done efficiently using a bulk-delete action that
deletes from the relation all tuples in the entire key space .
1
;
1
(see Chap.
10
).
Problems
8.1
Consider executing the transaction T
2
:
BD
Œ6DŒ7
AD
1
Œ7D
1
Œ6C
on the database indexed by the B-tree of Fig.
7.1
. 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-tree pages
occur during the execution of the transaction? What structure modifications are
performed? We assume redo-only modifications are used. Show the B-tree after
performing the forward-rolling phase of T
2
and after performing the whole of T
2
.
What log records are generated?
8.2
By outlining algorithms similar to
redo-page-split
(Algorithm
8.10
), verify
that the log records for the other four redo-only structure modifications (tree-
height increase, tree-height decrease, page merge, and records redistribute) allow
for selective redoing.
8.3
A simple and practical compression method called
prefix truncation
can be used
to save space in B-tree pages. For each leaf or non-leaf page p, we store the longest