Information Technology Reference
In-Depth Information
Proof
Analogous to that of Lemma
7.8
.
t
7.6
Traversals for Undo Actions
In Sect.
4.3
, the call
find-page-for-undo-insert
.q; x/ is used to locate and write-
latch the target data page in implementing logically the undo action I
1
Œx;
v
in the procedure
undo-insert
.n;T;p;x;n
0
/ (Algorithm
4.7
), and the call
find-
page-for-undo-delete
.q; x;
v
/ is used to locate and write-latch the target data page
in implementing logically the undo action D
1
Œx;
v
in the procedure
undo-
delete
.n;T;p;x;
v
;n
0
/ (Algorithm
4.9
). Both calls are assumed to perform any
structure modifications that are needed to accommodate the undo action.
As the undo actions are performed under the protection of the commit-
duration X locks obtained for the corresponding forward-rolling actions,
no next keys need be determined. Thus,
find-page-for-undo-insert
.p; x/ and
find-page-for-undo-delete
.p; x;
v
/ are just
find-page-for-delete
.p; p
0
;x;y/ and
find-page-for-insert
.p; p
0
;x;
v
;y/, respectively, simplified so that the next page
p
0
and next key y are not determined. Accordingly, the call
find-page-for-
update
.p; p
0
;x;
both
/ is only used with
both
D
false.
Example 7.11
Assume that page p
8
of the B-tree of Fig.
7.1
was created in a split of
page p
7
in the following way. Page p
7
contained tuples with keys 17, 18, 19, 21, and
22 at the time when transaction T
1
inserted into it a tuple with key 20, thus making
the page full. Then transaction T
2
inserted a tuple with key 24, causing a page split
in which the tuples with keys 20, 21, and 22 were moved to the new sibling page p
8
,
into which the tuple with key 24 went. Then T
2
deleted the tuple with key 22 and
committed. The pages p
7
and p
8
thus have the contents as shown in Fig.
7.1
.
Now T
1
is still active and wants to abort and roll back. In undoing the insertion of
the tuple with key 20, the attempt at physical undo fails because the tuple no longer
resides in the page, p
7
, mentioned in the log record for the insertion. Thus, a logical
undo must be performed. To that end, page p
7
is unlatched, and the call
find-page-
for-undo-insert
.p; 20/ is performed, returning p
D
p
8
, which can accommodate
the undoing.
The entire history of the two transactions is
AI
1
Œ20C
T
1
W
BI
Œ20
T
2
W
BI
Œ24DŒ22C
where the action I Œ20 is performed on page p
7
and the actions I Œ24, DŒ22 and
I
1
Œ20 on page p
8
.
t
As the procedure calls
find-page-for-undo-insert
.p; x/ and
find-page-for-undo-
delete
.p; x;
v
/ are only used in logical undo actions, that is, to perform an undo
action in the case in which an attempt at a physical undo fails, it is likely that the
leaf-level page on the saved path is not a correct page to start the top-down traversal.
This was the case in the example above. Thus, we suggest that in this case, the
