Information Technology Reference
In-Depth Information
scan forward
log
scan backward
& append
scan forward
analysis
pass
redo pass
(repeat history)
undo
pass
physical redo
physical or
logical
undo
active-transaction
&modified-page
tables
data
base
Fig. 4.2
Analysis, redo, and undo passes of the ARIES recovery algorithm
(a) The
P
AGE
-LSN
value stamped on a version of a page p always indicates that all
updates with
LSN
s less than or equal to
P
AGE
-LSN
.p/ are present in page p,but
updates with
LSN
s greater than
P
AGE
-LSN
.p/ are not, thus correctly indicating
the state of the page.
(b) All redo actions can be performed physically on the same pages and at the same
record positions where they were performed originally by checking the
P
AGE
-
LSN
of the page. If
P
AGE
-LSN
is less than the
LSN
of the log record, then the
logged update is missing from the page and must be redone.
(c) Any new log records need not, and must not, be written for the redo actions,
because, by (b), the redo actions are exactly represented by the log records
written for the original update actions.
(d) Undo actions are always legal so that there is no need to check whether or not
they can be performed, provided that the transactions have been run sufficiently
isolated (an issue to be discussed later).
Example 4.2
With the do-redo-undo recovery paradigm, restart recovery is per-
formed as follows in the scenario of Example
4.1
(Fig.
4.1
). First, the updates of
both transactions are redone physically on the disk version of page p fetchedtothe
buffer:
1. When the effects of both updates are missing from the disk version of page p,
the
P
AGE
-LSN
is less than the
LSN
s of both updates, and hence both updates are
redone on p.
2. When the effect of the first update is in the disk version of p but the second is
missing, the
P
AGE
-LSN
is greater than or equal to the
LSN
of the first update, and
hence only the second update is redone.
3. When both updates are in the disk version of p,the
P
AGE
-LSN
is greater than or
equal to the
LSN
of the second update, and hence neither update is redone.
