Transaction Rollback and Restart Recovery - Transaction Processing - page 93

Algorithm 4.17 Procedure analyze-smo .r/
if r is of the form “n WhS; p 1 ;:::;p k ;V 1 ;:::;V l i” then
for i D 1;:::;k do
if there is no entry for p i in the modified-page table then
insert .p i ; R EC -LSN D n/ into the modified-page table
end if
end for
end if
In the redo pass (Algorithm 4.14 ), the logged structure modifications are redone,
one page at a time, as the update actions by transactions, when it turns out that the
result of the modification is not present in the page. The log records for structure
modifications are processed by the call redo-smo .r/ (Algorithm 4.18 ).
We assume that the effect of a structure modification on each single page involved
is encoded in the log record in such a way that the modification on that page can
be redone using only that page possibly with some other, non-page arguments in
the log record. In other words, we assume that the log record allows for selective
redoing , so that the effects of the modification on any single page involved can be
accomplished without inspecting the contents of the other pages mentioned in the
log record.
For example, using the log record n: h page-split ;p;q;x;q 0 ;s;V;h i , (1) the effect
of the split on page q can be redone by deleting from q all records with keys greater
than or equal to x, (2) the effect on q 0 by formatting q 0 as an empty B-tree page and
inserting into it the records from the set V , (3) the effect on the space-map page s
by setting the bit corresponding to q 0 , and (4) the effect on the parent page p by
inserting into it the child-router record .x; q 0 /.
Algorithm 4.18 Procedure redo-smo .r/
if r is of the form “n WhS; p 1 ;:::;p k ;V 1 ;:::;V l i” then
for all i D 1;:::;k do
if there is no entry for page p i in the modified-page table then
insert .p i ; R EC -LSN D n/ into the modified-page table
end if
if R EC -LSN.p i / n then
fix-and-write-latch .p i /
if page p i is unmodified then
R EC -LSN.p i / maxfR EC -LSN.p i /; P AGE -LSN.p i /C1g
end if
if P AGE -LSN.p i /<n then
using the arguments V 1 ;:::;V l from the log record, apply the effect of structure
modification S onto page p i
P AGE -LSN.p i / n
end if
unlatch-and-unfix .p i /
end if
end for
end if