Information Technology Reference
In-Depth Information
set (relation). Similarly, if the pages of the physical database where the tuples are
stored are selected as data items, insertions and deletions of tuples can be modeled
as write actions on a page. In both cases, transaction management is rather coarse
grained: the log must record changes to a whole relation or page, and the unit of
synchronization for managing concurrency (the lockable unit) is a whole relation or
page.
In modern database management systems, individual tuples are used in log
records and in locking (as the most fine-grained units). In this case, when a
transaction T
1
has updated a page and is still active, another transaction T
2
can
update the same page. It is also allowed that, due to a structure modification (such
as a page split in a B-tree) caused by T
2
, the tuple that T
1
updated on page p will be
moved to another page p
0
while T
1
is still active.
1.8
The Key-Range Model
In the transaction model used throughout this topic and termed the
key-range model
,
read actions return the least key in a given
key range
, and the update actions are
insertions and deletions of tuples with a given key.
The set of key values for the tuples is assumed to be totally ordered. The ordering
is denoted
and its inverse relation
; the respective irreflexive ordering relations
are referred to in the familiar way as < and >. The least possible key value is
1
,
and the largest is
1
; we assume that these do not appear in any tuple in the actual
database.
The key-range model is sufficient to model the most important principles
that are used in physiological log-based recovery and tuple-level concurrency
control (key-range locking of a unique key). The model can also be used to
describe, in a natural manner, isolation anomalies (see Sect.
5.3
) coming from
concurrent key-range reads and insertions and deletions of individual tuples (for
instance, the phantom phenomenon; see Sects.
1.6
and
5.3
and Example
1.9
below).
In the key-range model, a transaction on the database r can contain, besides
the begin-transaction action B, the abort-transaction action A and the commit-
transaction (or complete-rollback) action C , the following four types of forward-
rolling database actions:
1.
Read-first actions
of the form
RŒx;
z
;
v
(1.8)
for reading the tuple .x;
v
/ with the first key value x that satisfies the condition
x
z
. The key value
z
is an input parameter, and the key x and the value
v
are output parameters. The action fetches the tuple .x;
v
/ whose key is the least
key satisfying x
z
and .x;
v
/
2
r . If no such tuple exists, .
1
;0/ is returned.
Shorthand notations for this action are RŒx;
z
, RŒx;
v
,orRŒx.
