Information Technology Reference
In-Depth Information
Algorithm 4.7
Procedure
undo-insert
.n;T;p;x;n
0
/
fix-and-write-latch
.p/
if
P
AGE
-LSN.p/ 6D n and, in addition, either p isnotadatapageorp does not contain the tuple
.x;
v
/ or p would underflow due to the deletion of .x;
v
/
then
unlatch-and-unfix
.p/
find-page-for-undo-insert
.q; x/
p q
end if
undo-insert-onto-page
.T;p;x;n
0
/
unlatch-and-unfix
.p/
Algorithm 4.8
Procedure
undo-insert-onto-page
.T;p;x;n
0
/
delete the tuple .x;
v
/ from page p
log
.m;hT; I
1
;p;x;n
0
i/
P
AGE
-LSN.p/ m
U
NDO
-N
EXT
-LSN.T / n
0
Similarly to
undo-insert
, the call
undo-delete
.n;T;p;x;
v
;n
0
/ (Algorithm
4.9
)
executes the undo action D
1
Œx;
v
of a delete action DŒx;
v
performed by T on
p and logged with
LSN
n. Again 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
.Even
if the
P
AGE
-LSN
has advanced, p is still the correct target page when p is a data
page and covers the key x and has room for the tuple .x;
v
/. (In the case of a B-tree
page, we can be sure that the page covers x if x is between the least and greatest
keys currently in the page, although this test will miss some cases in which p still
covers x.)
Otherwise, page p is unlatched and unfixed, and the call
find-page-for-undo-
delete
.q; x;
v
/ is used to locate the correct target page and to perform any structure
modifications (page splits) needed to prevent the target data page from overflowing.
The tuple .x;
v
/ is inserted into target page, the insertion is logged with a redo-
only log record (
3.13
), and the
P
AGE
-LSN
ofthepageandthe
U
NDO
-N
EXT
-LSN
of the
transaction are updated by the procedure
undo-delete-onto-page
.T;p;x;n
0
/.
Algorithm 4.9
Procedure
undo-delete
.n;T;p;x;
v
;n
0
/
fix-and-write-latch
.p/
if
P
AGE
-LSN.p/ 6D n and, in addition, either p is not a data page of r or p does not cover the
key value x or p does not have room for the tuple .x;
v
/
then
unlatch-and-unfix
.p/
find-page-for-undo-delete
.q; x;
v
/
p q
end if
undo-delete-onto-page
.T;p;x;
v
;n
0
/
unlatch-and-unfix
.p/
