Information Technology Reference
In-Depth Information
a
f
:
p
:
b
f
:
p
:
q
:
(
x, v
)
Fig. 2.6
Organization of a heap as a chain of pages. (
a
)Pagep is full; (
b
) insertion IŒx;
v
causes
a new page q to be allocated and linked into the end of the heap
Consider the case where an insert action IŒx;
v
by transaction T
1
causes the
allocation of a new page q and linking it to the end of the heap, to be the follower
of the last page p. Because the structure needs to be kept consistent during normal
transaction processing, four pages must be kept write-latched for the duration of the
allocation (and its logging): the page s that contains the space map, the last page p,
the page q that is to be linked, and the first page f . Note that all these pages are
updated in the allocation. Page q that will receive the tuple .x;
v
/ must be formatted
as an empty data page. Page q is kept write-latched until the tuple .x;
v
/ has been
inserted into page q and the insertion has been logged.
Assume that another transaction now performs the action IŒy;
w
(where y
6D
x).
This insertion also goes to page q in the heap structure. When process thread that
executes transaction T
1
releases its write latch acquired for the insertion IŒx;
v
,the
process thread executing T
2
is free to write-latch page q and to insert the tuple .y;
w
/
there.
Then T
2
commits while T
1
is still active and then wants to abort. In the backward-
rolling phase, the undo action I
1
Œx;
v
is executed so as to delete the tuple .x;
v
/
from page q. However, the allocation of page q obviously must not be undone: T
2
has already made its own update on page q and committed.
t
We conclude that a structure modification must be allowed to “commit” once it
is successfully completed, regardless of the eventual outcome of the transaction that
caused the structure modification.
Transaction processing thus involves operations at two levels. At the higher, or
logical level
, we have actions of transactions operating on the logical database, and
at the lower, or
physical level
, we have operations on the pages of the physical
database. The two levels are interconnected so that each action at the logical level,
when performed on a given state of the physical database, is mapped to a sequence
of page-wise operations at the physical level.
