Information Technology Reference
In-Depth Information
Algorithm 4.16
Procedure
undo-pass
./
for
each forward-rolling transaction T in the active-transaction table
do
abort
.T /
end for
while
the active-transaction table is nonempty
do
n maxfU
NDO
-N
EXT
-LSN.T / j T is in the active-transaction tableg
r
get-log-record
.n/
if
r is “n WhT; Bi”
then
log
.m;hT; Ci/
flush-the-log
./
delete the record of T from the active-transaction table
else if
r is “n WhT; I; p; x;
v
;n
0
i”
then
undo-insert
.n;T;p;x;n
0
/
else if
r is “n WhT; D; p; x;
v
;n
0
i”
then
undo-delete
.n;T;p;x;
v
;n
0
/
else if
r is “n WhT; SŒP ; n
0
i”
then
U
NDO
-N
EXT
-LSN.T / n
0
end if
end while
Example 4.7
In the case of our running example, the undo pass is performed as
follows. First, the only forward-rolling transaction, T
3
, is turned into backward-
rolling by appending the abort log record
119:
h
T
3
;A
i
to the log buffer and by setting the state of T
3
as “backward-rolling” in the active-
transaction table. The contents of the active-transaction table are now:
f
.T
2
; backward-rolling;
U
NDO
-N
EXT
-LSN
D
110/,
.T
3
; backward-rolling;
U
NDO
-N
EXT
-LSN
D
112/
g
.
Then the log is scanned backwards starting from the log record with
LSN
112
D
max
f
110; 112
g
(the maximum of the
U
NDO
-N
EXT
-LSN
s in the active-transaction
table).
The log record with
LSN
112 was written for an action IŒx
2
;
v
2
performed by
T
3
on page p
2
.Thus,pagep
2
is fixed and write-latched. We observe that the tuple
with key x
2
still resides in page p
2
and that the page does not underflow if the tuple
is deleted. The undo action I
1
Œx
2
;
v
2
is thus performed physically by deleting the
tuple .x
2
;
v
2
/ from page p
2
. The redo-only log record
120:
h
T
3
;I
1
;p
2
;x
2
; 111
i
is appended to the log buffer,
P
AGE
-LSN
.p
2
/
120 is set, page p
2
is unlatched and
unfixed, and
U
NDO
-N
EXT
-LSN
.T
3
/
111 is set in the active-transaction table.