Information Technology Reference
In-Depth Information
With key-range locking, all the tuples in r are S-locked, meaning that the entire
key space .
1
;
1
is S-locked, even though only a small subset qualifies for P .
With multi-granular locking (presented in Sect.
9.2
), a single S lock would be used
to lock the entire relation r .
We would like to lock only those tuples that qualify for the query predicate P .
In
predicate locking
, the lock names are predicates over the attributes of the logical
database, such as
x<X<y
^
X
6D
z
^
V
v
.
A query with such a predicate P as the query predicate would be protected by a
predicate lock of mode S and name P . An update action WŒx;
u
;
v
, generated from
update
r
set
V
D
v
where
X
D
x,
would be protected by a predicate lock of mode X and name
X
D
x
^
.V
D
u
_
V
D
v
/.
Two predicate locks with names P
1
and P
2
are incompatible if their modes are
incompatible and the conjunction P
1
^
P
2
is satisfiable.
The main problem with general predicate locks is the complexity of testing their
incompatibility. Recall that satisfiability of general boolean predicates is an NP-
complete problem. The incompatibility test cannot be reduced to an equality test
between two simple hash values computed from the predicates. For this reason,
general predicate locking is not applied in concurrency control of transactions.
The key-range locking protocol can be regarded as an efficient implementation
of predicate locking that uses a very simple form of predicates, namely:
“x
X>
z
,” for RŒx; >
z
;
v
.
“x
X
z
,” for RŒx;
z
;
v
.
“X
D
x,” for IŒx;
v
or DŒx;
v
.
The implementation by key-range locking is conservative in that more is locked
than is implied by the above predicate locks. Assume that x is a key which is or is
not in the current database and let x
0
be the greatest key less than x in the database
(if such a key exists) or
1
(otherwise). The S lock on x acquired for RŒx; >
z
;
v
or RŒx;
z
;
v
actually locks the predicate “x
X>x
0
,” even if
z
>x
0
.The
commit-duration X lock acquired for IŒx;
v
on x actually X-locks the predicate
“x
X>x
0
.” The commit-duration X lock acquired for DŒx;
v
on the next key y
of x actually X-locks the predicate “y
X>x
0
.”
Example 6.21
The following histories, although free of anomalies, are not possible
under the key-range locking protocol when run on the database
f
.2;
u
/
g
:
1. B
1
R
1
Œ2; > 1;
u
B
2
I
2
Œ1;
v
.
2. B
1
I
1
Œ3;
v
B
2
D
2
Œ2;
u
.
3. B
1
I
1
Œ4;
v
B
2
I
2
Œ3;
w
.
4. B
1
D
1
Œ2;
u
B
2
I
2
Œ1;
v
.
5. B
1
D
1
Œ2;
u
B
2
R
2
Œ
1
;>2;0.
