Information Technology Reference
In-Depth Information
The found next key y is conditionally X-locked for commit duration. If the lock
is granted, the call
delete-from-page
.T;p;x/ (Algorithm
3.2
) given in Sect.
3.6
is
used to perform and log the deletion of the tuple with key x from page p,after
which the pages p and p
0
are unlatched and the lock on x released. Otherwise, the
P
AGE
-LSN
s of pages p and p
0
are saved, the pages are unlatched, the lock on y is
requested unconditionally, and, when the lock is granted, the pages are relatched.
After relatching the pages p and p
0
, the page contents are inspected so as to find
out whether or not they can still be used to satisfy the delete action. The delete action
can be satisfied if one of the following two conditions holds:
1.
P
AGE
-LSN
.p/ and
P
AGE
-LSN
.p
0
/ have not advanced from the saved values.
2. p
D
p
0
and
P
AGE
-LSN
.p/ has advanced from the saved value, but page p is still a
data page with x
1
x
x
2
where x
1
is the least and x
2
the greatest key in page
p,pagep does not underflow by the deletion of a single tuple, and y is the least
keyinpagep greater than x.
Otherwise, we must unlatch the pages p and p
0
, unlock key y, and repeat the
search for the pages and the next key by performing again the call
find-page-for-
delete
.p; p
0
;x;y/, locking the found key y conditionally, and so on.
Obviously, because of the use of conditional lock calls, no deadlocks can be
caused by the interplay of locks and latches in Algorithms
6.6
-
6.8
. In Chap.
7
we
give deadlock-free algorithms for the procedures
find-page-for-read
,
find-page-for-
insert
,and
find-page-for-delete
used in Algorithms
6.6
-
6.8
. This means that for any
set of concurrent transactions, where each transaction consists of only a single action
(a read, an insert, or a delete action), no deadlock can occur. Note that the two keys
locked in the insert and delete algorithms are locked in ascending key order, and no
lock is ever upgraded.
Unfortunately, there is no upper limit on the number of iterations of the
while
loop in Algorithms
6.6
-
6.8
. Thus, with key-range locking, there is no upper limit
on the access-path-length of read, insert, and delete actions:
starvation
may occur.
We will discuss this problem later.
6.8
Predicate Locking
Assume that a transaction reads a set of tuples from r.X;V/using an
SQL
query
select
from
r
where
P ,
where P is a predicate over X and V .IfP is more complicated than a single
primary-key range or a union of primary-key ranges, then in our key-range
transaction model, the query must be mapped to the action sequence
RŒx
1
;>
1
;
v
1
; RŒx
2
;>x
1
;
v
2
:::RŒx
n
;>x
n1
;
v
n
RŒ
1
;>x
n
;0
that reads all the tuples from r . The program generating the transaction then checks
at each tuple .x
i
;
v
i
/ whether or not it qualifies for P .
