Information Technology Reference
In-Depth Information
records were first used to undo the updates done by active transactions (the “undo”
phase) and then to redo only the updates done by committed transactions that were
missing from the disk version of the database (the “redo” phase). The motivation for
this paradigm seems to be that since all the active transactions are eventually aborted
and rolled back, it is a waste of time to redo the updates of active transactions but
only those of the committed transactions. This recovery paradigm is presented in
several textbooks on database management.
Unfortunately, the do-undo-redo paradigm has major drawbacks that make it
difficult or impossible to apply in the transaction-processing environment con-
sidered in this topic. First, and most importantly, the do-undo-redo paradigm is
incompatible with physical redo and fine-grained transaction processing where a
page can contain uncommitted updates by several transactions. It may be impossible
to redo physically a committed update after rolling back an uncommitted update
that was performed on the page earlier than the committed update (as shown in case
(1) of the example below). As redoing can no longer be physical, we must resort
to logical redo, implying that new log records need to be written for redo actions.
Moreover, undo actions need to check whether or not they should be performed, and
the
P
AGE
-LSN
values stamped on pages no longer correctly indicate the state of the
pages.
Example 4.1
Assume that transaction T
1
performs the action DŒx;
v
to delete a
tuple .x;
v
/ from a full data page p and that then another transaction T
2
performs
the action IŒy;
w
to insert a tuple .y;
w
/ into page p, consuming the space created
by the deletion of .x;
v
/.ThenT
2
commits, but T
1
is still forward-rolling at the time
the system crashes (Fig.
4.1
). As T
2
committed before the crash, the log record of
its insert action IŒy;
w
and thus also the log record of the delete action DŒx;
v
of
T
1
were flushed onto the log disk before the crash. With the do-undo-redo recovery
paradigm, T
1
is first aborted and rolled back, after which the updates of T
2
are
redone.
We have three cases (as depicted in Fig.
4.1
) to consider:
Crash!
T
1
:
...
D
[
x, v
]
...
...
T
2
:
...
I
[
y,w
]
C
p
:
p
:
p
:
x, v
y,w
Fig. 4.1
A problem scenario
for do-undo-redo recovery
(1)
(2)
(3)
