Information Technology Reference
In-Depth Information
Algorithm 4.10
Procedure
undo-delete-onto-page
.T;p;x;
v
;n
0
/
insert the tuple .x;
v
/ into page p
log
.m;hT; D
1
;p;x;
v
;n
0
i/
P
AGE
-LSN.p/ m
U
NDO
-N
EXT
-LSN.T / n
0
We say that the
access-path-length
,or
path-length
for short, of a database action
(read or update) is the number of pages that need to be latched to locate the target
page of the action. The path-length of an action depends on the physical database
structure underlying the logical database. For example, if the relation r.
X
;V/ is
organized as a sparse B-tree index (see Sect.
7.1
), the path-length of an insert or
a delete action includes the number of pages latched during the B-tree traversal
needed to locate the target page of the action. Such traversals are included in the
implementations of read, insert, and delete actions (Sect.
6.7
), as well as in the
implementations of undo-insert and undo-delete actions (the procedures
find-page-
for-undo-insert
and
find-page-for-undo-delete
).
As we shall see in Chaps.
6
and
7
, a single root-to-leaf traversal along the B-
tree may not be sufficient, because two paths may have to be traversed to locate the
key next to a given key and because the acquisition of appropriate key-range locks
to protect the action may require even more traversals when the traversals are to
be done in a deadlock-free manner. Thus the ultimate access-path-length may be a
multiple of the height of the B-tree. On the other hand, in the best case the path-
length may be only one if the path previously traversed by a server-process thread
is remembered (see Sect.
7.2
) and the traversal for the next action follows the same
path.
The path-length of an undo action may often be shorter than that of the
corresponding forward-rolling action, thanks to the possibility of doing physical
undo. When the page p on which the forward-rolling insert or delete action
was performed can accommodate the undo-insert or undo-delete action, no other
database pages besides p need be latched. Omitting any operations needed to locate
the log record of the forward-rolling action (by the procedure
get-log-record
), we
conclude that the path-length of the undo action is only one in the case of a physical
undo.
In the case that a physical undo is impossible, a logical undo must be performed,
which includes a traversal of the index structure. However, in such a traversal only,
the target page must be located, while no new locks are acquired, thus reducing the
number of retraversals needed (see Sect.
7.6
). We conclude that the path-length of
a logical undo-insert action I
1
Œx;
v
(resp. undo-delete action D
1
Œx;
v
)isnever
greater than that of the forward-rolling delete action DŒx;
v
(resp. insert action
IŒx;
v
), but probably less.
