Information Technology Reference
In-Depth Information
4.3
Performing the Undo Actions
An undo action by a backward-rolling transaction or by a forward-rolling transaction
that does a partial rollback is performed using as an argument the log record for the
corresponding forward-rolling update action. The undo action o 1 ΠN x of an update
action oΠN x is first tried physically, that is, directly on the data page on which the
action oΠN x was performed. The page-id of that page is found in the log record for
N x.Ifsucha physical undo is impossible, we resort to a logical undo : the execution
of the undo action begins with a search of the database structure in order to locate
the current target page of the action.
When an undo action I 1 Œx; v must be performed logically, we assume that the
data page q that currently holds the tuple .x; v / is located and fixed and write-latched
by the call
find-page-for-undo-insert .q; x/,
which is also assumed to take care of any structure modifications needed. These
arrange that page q will hold a sufficient number of tuples even after the deletion
of .x; v /. Similarly, when an undo action D 1 Œx; v is performed logically, the
data page q that covers key value x is located and fixed and write-latched by the
call
find-page-for-undo-delete .q; x; v /,
which also takes care of any structure modifications needed to arrange sufficient
space for the tuple .x; v / to be inserted. Implementations for these calls are given
in Chaps. 7 and 8 for the case in which the physical database is a sparse B-tree (see
Sect. 7.6 , in particular).
The call undo-insert .n;T;p;x;n 0 / (Algorithm 4.7 ) executes the undo action
I 1 Œx; v of an insert action IŒx; v that was performed by transaction T on data
page p and logged with LSN n. The new value of U NDO -N EXT -LSN .T / becomes n 0
after the undo action. A physical undo is always possible if the P AGE -LSN of page p
is still equal to the LSN found in the log record for IŒx; v , because in that case the
contents of the page have not changed in between. On the other hand, even if then
P AGE -LSN has advanced, p may still be the correct target page; this is true when p is
still a data page and contains the tuple .x; v / and a sufficient number of other tuples
so that the page will not underflow when .x; v / is deleted.
Otherwise, page p is unlatched and unfixed, and the call find-page-for-undo-
insert .q; x/ is used to locate the correct target page and to perform any structure
modifications (page merges) needed to prevent the target data page from underflow-
ing. Finally, when the correct target page has been found, the tuple .x; v / is deleted,
the deletion is logged with a redo-only log record ( 3.12 ), and the P AGE -LSN of the
page and the U NDO -N EXT -LSN of the transaction are updated by the procedure undo-
insert-onto-page .T;p;x;n 0 / (Algorithm 4.8 ).
Search WWH ::




Custom Search