Information Technology Reference
In-Depth Information
1. The modified page p was not flushed onto disk before the crash, so that both
updates are missing from the disk version of page p. In other words, page p
contains .x;
v
/, but not .y;
w
/.
2. Page p was flushed onto disk between the two updates, so that the disk version
of p contains neither .x;
v
/ nor .y;
w
/.
3. Page p was flushed onto disk after the two updates before the crash, so that the
disk version of p contains .y;
w
/, but not .x;
v
/.
In case (1) the effects of the deletion DŒx;
v
by T
1
and the insertion IŒy;
w
by
T
2
are not present in the disk version of page p, so the deletion must not be undone,
but the insertion, being an update by a committed transaction, must be redone. But
redoing the insertion on the full page p is not possible. Thus, we must resort to
a
logical redo
: the physical database must be searched for another data page into
which the tuple .y;
w
/ can be inserted. As regards the physical database, this new
insertion is different from the original insertion and hence must be logged with a
new physiological log record. Moreover, if the physical database is a B-tree, the
page p must be split so as to accommodate the insertion, and that split must also be
logged.
In case (2) the effect of the deletion DŒx;
v
by T
1
is present in the disk version
of p, but the effect of the insertion IŒy;
w
by T
2
is not. Thus the deletion must be
undone and the insertion redone. The undo action D
1
Œx;
v
is performed on page
p. If the undo action is logged as usual, with a redo-only log record, and the
LSN
of
that log record is stamped into the
P
AGE
-LSN
field of p, then the
P
AGE
-LSN
becomes
greater than the
LSN
of the log record for IŒy;
w
which should be redone. Thus, we
can no longer rely on the
P
AGE
-LSN
value of a page in deciding which updates on
that page should be redone.
In case (3) the effects of the deletion DŒx;
v
and the insertion IŒy;
w
are both
present in the disk version of p, so the deletion must be undone, but the insertion
must not be redone. As page p is full, the undo action D
1
Œx;
v
is performed
logically. This is the only of the three cases that does not exhibit a problem.
t
4.6
The ARIES Do-Redo-Undo Recovery Algorithm
The
ARIES
recovery algorithm
(Algorithm for Recovery and Isolation Exploit-
ing Semantics) first implemented in the
IBM DB2
database management system
is based on the
do-redo-undo
recovery paradigm, in which the entire (recent)
history is first repeated, so that the missing updates by all transactions are first
redone in their original chronological order and only then the updates by active
transactions are undone with each undoing logged with a redo-only log record
(Fig.
4.2
). This approach ensures that the following properties hold in fine-grained
transaction processing in which a data page can hold updates by several active
transactions:
