Information Technology Reference
In-Depth Information
9.1
Key-Range Locking for Multiple Granules
In this section we discuss how the key-range locking protocol defined in Sect.
6.4
generalizes to the situation in which the logical database consists of a hierarchy
of data items of different granules, as discussed in Sect.
1.10
. For instance, the
entire logical database may be composed of databases of multiple users, each user
database of multiple relations, and each relation of multiple tuples. In this setting it
is useful if larger-granule data items can be locked (with one or two locks) without
the need to acquire explicit locks on all the smaller-granule data items contained
in it, when we want to operate on all the contained smaller-granule data items. For
instance, if we want to read all tuples from a relation, then it certainly seems more
practical to acquire just a single S lock on the relation instead of locks on every
tuple in the relation.
We assume that the units at all levels or at some specified levels of the granule
hierarchy are termed
lockable units
that can be locked. In the case of a three-level
granule hierarchy, when the units at all the levels are lockable, this means that
locks can be acquired (1) on the whole database b, (2) on individual relations r
in database b,and(3)onkeysx of tuples in relation r . The names of these locks
are, respectively, b, .b; r/,and.b;r;x/ or actually 4-byte hash values calculated
from them.
For the action RŒb; r
0
;r;R
0
of browsing the schema of a relation r
0
in
database b, transaction T must acquire a commit-duration S lock on the relation
identifier .b; r
0
/. For the action IŒb;r;R of creating a new relation r , T must
acquire a commit-duration X lock on .b; r/ and a short-duration X lock on relation
identifier .b; r
0
/,wherer
0
is the relation next to r in database b. For the action
DŒb; r; R of dropping a relation r , T must acquire a short-duration X lock on .b; r/
and a commit-duration X lock on the next relation .b; r
0
/. This protocol prevents
dirty creations and droppings of relations and dirty and unrepeatable schema reads
(including phantom relations).
Isolation anomalies must now also be defined between actions on a whole and its
parts, such as a relation and its tuples. For example, consider a transaction T
1
that
creates a new relation r or drops a relation r in database b. While T
1
is still active,
another transaction T
2
reads tuples of relation r or inserts or deletes tuples in r .The
read action by T
2
must be defined as a dirty read and the insert and delete actions as
dirty writes.
In the example, T
1
will protect its actions by acquiring X locks on the relation
.b; r/ and on the next relation .b; r
0
/, following the key-range locking protocol
applied at the relation level. The X lock on relation .b; r/ must mean that T
1
has
also locked (implicitly) all tuples in r . Likewise, an S lock on relation .b; r/ must
mean that all tuples in r are S-locked.
The problem is how to detect the incompatibility of locks on a relation .b; r/
and on a key .b;r;x/. One solution could be to organize the lock table into a
data structure that stores paths of the granule hierarchy. For example, when a
transaction T requests an m lock on relation .b; r/, the lock manager checks that
