Information Technology Reference
In-Depth Information
between a primary-key-based insert, delete, or write action and a secondary-key-
based delete or write action. Secondary-key-based read actions cause new kinds of
dirty and unrepeatable reads. We leave the details of the definitions as exercises (see
the Problems section).
The key-range locking protocol must be generalized accordingly. In
key-specific
(or
index-specific
)
key-range locking
, names of finest-granular locks on a relation r
are triples .r;X;x/ (or actually 4-byte hash values computed from them), where r
is the identifier of the relation, X is the identifier of the attribute sequence used as
the key, and x is a key value. In the case of our example relation r.X;Y;V/,lock
names are thus of the forms .r;X;x/and .r;Y;y/.
Key-specific locks make the granule hierarchy of lockable data items a directed
acyclic graph: in the case of a relation r with primary key X and secondary keys
Y
1
;:::;Y
n
,therearen
C
1 (logical) access paths from r to any tuple in r . Read
actions can be protected with locks on granules along a single path to the target
tuple, namely, the one defined by the key whose range is read, if only insert, delete,
and write actions are protected by locks along every path to the target tuple.
With key-specific locking, a primary-key-based read action RŒx;
z
;y;
v
on
relation r is protected by an IS lock on r and an S lock on .r;X;x/, and a secondary-
key-based single-tuple read action RŒx; y;
z
;
v
(for unique key Y ) is protected by
an IS lock on r and an S lock on .r;Y;y/.
For a primary-key-based bulk-read action R
X
Œs
X
;s
XYV
, an IS lock is acquired on
r and, for each range in s
X
, S locks are acquired on all .r;X;x/ with .x; y;
v
/
2
r
and x in the range. Moreover, if no tuple in r has the upper bound of the range as its
primary key, an S lock is also acquired on .r;X;x
0
/ where x
0
is the key next to the
upper bound of the range.
Similarly, for a secondary-key-based bulk-read action R
Y
Œs
Y
;s
XYV
,anISlockis
acquired on r and, for each range in s
Y
, S locks are acquired on all .r;Y;y/ with
.x; y;
v
/
2
r and y in the range, and, if no tuple in r has the upper bound of the
range as its secondary key, an S lock is also acquired on .r;Y;y
0
/ where y
0
is the
key next to the upper bound of the range.
For an insert action IŒx;y;
v
, a commit-duration IX lock is acquired on r ,
commit-duration X locks are acquired on .r;X;x/ and .r;Y;y/, and short-duration
X locks (or just IX locks, cf. Problem
9.3
) are acquired on .r;X;x
0
/ and .r;Y;y
0
/,
where x
0
is the key next to x and y
0
is the key next to y.
For a delete action DŒx; y;
v
, a commit-duration IX lock is acquired on r ,
short-duration X locks are acquired on .r;X;x/ and .r;Y;y/, and commit-duration
X locks are acquired on .r;X;x
0
/ and .r;Y;y
0
/,wherex
0
is the key next to x and y
0
is the key next to y.
Example 11.1
Assume that the contents of the database are initially
f
.1; 40;
v
1
/; .3; 20;
v
3
/; .4; 50;
v
4
/; .5; 60;
v
5
/; .6; 60;
v
6
/
g
:
