Information Technology Reference
In-Depth Information
a
c
b
Fig. 9.4
Possible scenarios (
a, b
) and an impossible scenario (
c
) in multi-granular locking
Scenario (c) is prevented by the locking protocol, because the lock modes IX and
SIX are incompatible, or, actually, because IX and S are incompatible (recall that
SIX
D
S + IX).
t
The following theorem states the fundamental property of the multi-granular
locking protocol, namely, that the incompatibility of implicit locks is detected:
Theorem 9.3
Assume the multi-granular locking protocol with lock modes S, X, IS,
IX, SIX.
(a) If transaction
T
1
holds an explicit lock on data item
x
1
and transaction
T
2
holds
an explicit or implicit X lock on data item
x
2
,then
x
1
6D
x
2
and
x
1
are not
contained in
x
2
.
(b) If transaction
T
1
holds an explicit X lock on data item
x
1
and transaction
T
2
holds an explicit S lock or SIX lock or an implicit S lock on data item
x
2
,then
x
1
6D
x
2
and
x
1
are not contained in
x
2
.
Proof
Because T
2
holds an explicit or implicit lock on x
2
, there must exist a data
item x
0
2
explicitly locked by T
2
such that x
0
2
D
x
2
or x
0
2
contains x
2
.Forthesakeof
contradiction, assume that x
1
D
x
2
or x
1
is contained in x
2
.Thenx
0
2
is on the path
from the root of the granule hierarchy down to x
1
. In case (a), the explicit lock on x
0
2
held by T
2
is an X lock. By the locking protocol, because T
1
holds an explicit lock
on x
1
, it should also hold some lock on x
0
2
, which however is not possible, because
the lock mode X is incompatible with all lock modes. In case (b), the explicit lock
on x
0
2
held by T
2
is an S lock or a SIX lock. By the locking protocol, T
1
should also
hold an IX lock (or a SIX lock) on x
0
2
, which however is not possible, because the
lock modes IX and SIX are incompatible with the lock modes S and SIX.
t
The granule hierarchy of lockable units can also consist of parts of the physical
database, or logical and physical parts can be mixed up. For instance, the hierarchy
could be system, database, file, page, and tuple.
Sometimes, intention locks are not required all the way from the top of the
hierarchy (i.e., the whole system): it is possible to start from a lower level (such
as a database) and proceed downwards. If the creation and destroying of databases
are specified to be special operations that happen outside normal user transactions,
