Information Technology Reference
In-Depth Information
With redo-only structure modifications, each log record must carry all the
information needed to redo the effects on all the pages involved in the modification,
which means that such a log record tends to be large in size. The log record for
a page split occupies about half a page, that for a records redistribute at most half
a page, that for a tree-height increase a full page, and those for a page merge and
tree-height decrease at most a full page. Thus, in each case it is possible to fit each
log record in a single log-file page, even if no compression is used.
We may also allow a long log record to span two log-file pages, provided that the
header of the record gives the total record length or other indication that makes it
possible to find out if the record resides in its entirety in a single page or continues
in the next page. Now if in recovery from a failure it is found that only a prefix of the
last log record has survived on the log disk, then that log record is simply omitted
in the recovery process. Naturally, with write-ahead logging, no updated page can
appear on the database disk before the entire log record for the update appears on
the log disk.
Theorem 8.14
Let
b
be a consistent and balanced B-tree and let
H
be any history
of forward-rolling, backward-rolling, committed, and rolled-back transactions that
can be executed on
b
using the above algorithms. Then in the event of a process
failure or a system crash the analysis pass followed by the redo pass of the
ARIES
recovery algorithm transforms
b
into a consistent and balanced B-tree
b
0
with
db
.b
0
/
D
H
0
.
db
.b//;
where
H
0
is the prefix of
H
up to the last action whose entire log record is found
on the log disk after the failure. Assuming that no transaction in
H
0
does any dirty
write, the undo pass of
ARIES
recovery transforms
b
0
into a consistent and balanced
B-tree
b
00
with
db
.b
00
/
D
H
00
.
db
.b
0
//
D
H
0
H
00
.
db
.b//;
where
H
00
is any shuffle of the action sequences that are used to complete the active
transactions in
H
0
to rolled-back transactions.
Proof
Because each structure modification is logged with a single log record that
makes it possible to selectively redo physically the effect of the modification on
each page involved in the modification and because each insert, delete, undo-insert,
or undo-delete action of any transaction on a data page is logged with a log record
that makes it possible to redo the update physically on the page, and because write-
ahead logging is followed, the redo pass of
ARIES
recovery transforms the B-tree b
into a B-tree b
0
that existed at the time of writing the last log record that survived
on the log disk. By Theorem
8.12
, b
0
is consistent and balanced and indexes the
database current at that time.
Because of the absence of dirty writes, the history can be completed with the
sequences of undo actions needed to roll back the active transactions, where the
sequences can be shuffled in any order, by Theorem
5.25
. Because b
0
is consistent
