Information Technology Reference
In-Depth Information
Enforcing this restriction requires that the lock manager must be able to process
conditional lock requests
in addition to normal unconditional lock requests (that
can lead to waiting).
A d -duration m lock for transaction T
on data items x can be requested
conditionally with the call
conditionally-lock
.T;x;m;d/
to the lock manager. The call returns with the lock granted if the lock could be
granted immediately (i.e., no incompatible locks were held by other transactions) or
with the response “lock not granted” otherwise.
The use of unconditional lock requests leads to the following sequence of
operations:
1. Locate and latch the target data page p.
2. Conditionally lock the target key x covered by page p.
3. If the lock was granted, go to step 6. Otherwise, save the
P
AGE
-LSN
of page p,
unlatch p, and unconditionally lock key x.
4. When the lock on x is granted, relatch page p and examine its
P
AGE
-LSN
.
5. If the
P
AGE
-LSN
is not changed from the saved value (i.e., the page has not been
updated in between) or if it can been seen from the current page contents that
page p is still the correct target page covering key x,gotostep6;otherwise,
unlatch p andgotostep1.
6. Perform the action on the tuple with key x on page p.
Examples of the need of this kind of operation sequences are given in the next
section.
6.7
Algorithms for Read, Insert, and Delete Actions
In the implementation of the key-range locking protocol for the logical database
actions RŒx;
z
;
v
, IŒx;
v
,andDŒx;
v
, we apply a conditional lock request while
holding the target data page latched. For the read action RŒx;
z
;
v
(Algorithm
6.6
),
the S lock on x is requested conditionally after the page holding the least key
x with x
z
has been located and latched. For the insert and delete actions
IŒx;
v
and DŒx;
v
(Algorithms
6.7
and
6.8
), the X lock on the key y next to
x is requested conditionally after the page holding that key has been located and
latched.
We have to make some assumptions about the underlying physical database
structure that stores the tuples of the relation r.X;V/. The data pages of the
physical database allocated for r must partition the entire key space Œ
1
;
1
/ into
disjoint key ranges Œl
i
;h
i
/, i
D
1;:::;n, one for each allocated data page p
i
.More
specifically, each page p
i
covers
its key range Œl
i
;h
i
/, that is, contains only tuples
.x;
v
/ with l
i
x<h
i
, and the key ranges satisfy the following conditions: (1)
l
1
D1
,(2)l
i
<h
i
D
l
iC1
for i
D
1;:::;n
1,and(3)h
n
D1
(Fig.
6.6
). We
