Information Technology Reference
In-Depth Information
However, all are possible under predicate locking:
1. T
1
S-locks “1<X
2”andT
2
X-locks “X
D
1.”
2. T
1
X-locks “X
D
3”andT
2
X-locks “X
D
2.”
3. T
1
X-locks “X
D
4”andT
2
X-locks “X
D
3.”
4. T
1
X-locks “X
D
2”andT
2
X-locks “X
D
1.”
5. T
1
X-locks “X
D
2”andT
2
S-locks “2<X
1
.”
The histories are permitted because in each case the conjunction of the names of the
locks acquired by T
1
and T
2
is not satisfiable.
t
Another drawback with key-range locking is that the name of one of the locks
needed for an insert action IŒx;
v
or a delete action DŒx;
v
, namely, the lock on the
next key, can only be determined after accessing the page that holds the next key.
Moreover, as shown above, implementing this in a deadlock-free manner requires
the use of conditional lock requests. With predicate locking, only one lock is needed
for an insert or a delete action, and that lock can be acquired before accessing the
target page.
A question arises whether there still might exist a reasonably efficient imple-
mentation for the simple case of predicate locks “x
X>
z
,” “x
X
z
,” and
“X
D
x.” The lock table then stores locks of the form .T;r;m;d/,wherer ,thelock
name, is a key range of one of the forms .
z
;x, Œ
z
;x,andŒx; x.
The lock table can be organized as follows. The X locks Œx; x for updates are
stored in a balanced search tree indexed by keys x. The S locks that protect ranges
of the forms .
z
;x or Œ
z
;x are stored in another balance search tree indexed by
the pairs .x;
z
/ of upper and lower bounds of the ranges. Obviously, locked ranges
with different upper bounds never overlap. Thus the question whether or not a given
key x
0
belongs to some S-locked range can be answered in time logarithmic in the
number of locked ranges stored in the tree. Similarly, inserting new locked ranges
and deleting existing locked ranges can be done in logarithmic time.
This organization is still less efficient than searching a hash-table bucket for
occurrences of the four-byte hash value computed from a given key, but it may
nonetheless be feasible in some cases. The problem with long keys of varying
lengths can be alleviated by truncating the keys from the tail to a prefix of fixed
maximum length, with, of course, the penalty of sacrificing in the accuracy of
locking.
Problems
6.1
Are the following histories possible under the read-write locking protocol?
(a) B
1
R
1
ŒxS
1
ŒP R
1
ŒyW
1
ŒxA
1
ŒP W
1
1
ŒxC
1
ŒP W
1
ŒyB
2
R
2
ŒxW
2
ŒxC
2
W
1
ŒxC
1
.
(b) B
1
R
1
ŒyS
1
ŒP R
1
ŒxW
1
ŒxA
1
ŒP W
1
ŒxC
1
ŒP B
2
R
2
ŒxW
2
ŒxC
2
R
1
ŒxW
1
ŒyC
1
.
What if transaction T
1
is run at
SQL
isolation level 2
ı
(read committed)?
