Information Technology Reference
In-Depth Information
The undo action D
1
Œx;
v
performed by transaction T on page p is logged with
the
undo-delete
log record
n
Wh
T; D
1
;p;x;
v
;n
0
i
;
(3.13)
when the log record for the respective forward-rolling delete action DŒx;
v
by T is
n
00
Wh
T; D; p
0
;x;
v
;n
0
i
for some n
00
<nand p
0
. In redoing the undo of a deletion
of a tuple, the entire tuple is needed and hence must be included in the log record. If
p
6D
p
0
, structure modifications occurred in the interim have caused that the correct
page to insert the tuple .x;
v
/ is no longer p
0
but p. In a B-tree, when a full page is
split into two pages, the key range covered by the page is split into two ranges, and
when two sibling pages are merged into a single page, the key ranges covered by
those pages are merged. Page p may, for example, be the result of merging page p
0
into its sibling page.
The log records for the above three undo actions are
redo-only log records
:using
one, the undo action given by the log record can be redone (physically), but undo
actions are never undone. The term
compensation log record
(
CLR
)isalsoused.
Note that the
U
NDO
-N
EXT
-LSN
value n
0
in the log record for the undo action is always
the same as in the log record for the corresponding forward-rolling action.
Example 3.1
The committed transaction
T
1
: BRŒx;
u
RŒy;
v
DŒ
z
;
w
I Œ
z
;
w
0
C
generates the log records:
n
1
:
h
T
1
;B
i
.
n
2
:
h
T
1
;D;p;
z
;
w
;n
1
i
.
n
3
:
h
T
1
;I;p
0
;
z
;
w
0
;n
2
i
.
n
4
:
h
T
1
;C
i
.
Here the tuple .
z
;
w
/ was deleted from page p, and the tuple .
z
;
w
0
/ was inserted
into page p
0
. The log sequence numbers n
1
;n
2
;n
3
;n
4
form an ascending sequence.
When other concurrent transactions are present, log records generated by them are
written in between T
1
's log records. The log records are chained backwards via the
U
NDO
-N
EXT
-LSN
s at update actions performed (Fig.
3.1
a).
t
Example 3.2
The rolled-back transaction
T
2
: BRŒx;
u
RŒy;
v
DŒ
z
;
w
I Œ
z
;
w
0
AI
1
Œ
z
;
w
0
D
1
Œ
z
;
w
C
generates the log records
n
1
:
h
T
2
;B
i
.
n
2
:
h
T
2
;D;p
1
;
z
;
w
;n
1
i
.
n
3
:
h
T
2
;I;p
2
;
z
;
w
0
;n
2
i
.
n
4
:
h
T
2
;A
i
.
n
5
:
h
T
2
;I
1
;p
3
;
z
;n
2
i
.
n
6
:
h
T
2
;D
1
;p
4
;
z
;
w
;n
1
i
.
n
7
:
h
T
2
;C
i
.
