Information Technology Reference
In-Depth Information
Example 6.7
The history H
1
of Example
6.5
is not possible under the key-range
locking protocol, because locks would be requested as follows:
1. For DŒ2;
v
, a short-duration X lock on key 2 and a commit-duration X lock on
the next key 3 for T
1
(both granted).
2. After DŒ2;
v
, the short-duration X lock held by T
1
on key 2 is released.
3. For RŒ3; >1;
w
, a commit-duration S lock on key 3 for T
2
(not granted).
Acquiring the S lock is not possible: T
2
must wait for the release of the commit-
duration X lock held by T
1
,thatis,forT
1
to commit or complete rollback.
t
Example 6.8
The history H
2
of Example
6.6
is not possible under the key-range
locking protocol, because locks would be requested as follows:
1. For RŒ3; >1;
w
, a commit-duration S lock on key 3 for T
1
(granted).
2. For IŒ2;
v
, a commit-duration X lock on key 2 (granted) and a short-duration
X lock on the next key 3 (not granted), for T
2
.
Acquiring the X lock on key 3 is not possible: T
2
must wait for the release of the
SlockheldbyT
1
,thatis,forT
1
to commit or complete rollback.
t
Along these lines, we now present a protocol that ensures full isolation for
transactions in our key-range transaction model. In this protocol, called the
key-
range locking protocol
(or
key-value locking protocol
), every transaction obeys the
following rules when acquiring and releasing locks:
1. For the read action RŒx;
z
;
v
, a commit-duration S lock is acquired on the key x
of the tuple .x;
v
/ to be read.
2. For the forward-rolling insert action IŒx;
v
, a commit-duration X lock is
acquired on the key x of the tuple .x;
v
/ to be inserted, and a short-duration
X lock is acquired on the
next key
y of x, that is, the least key y in the database
with y>x(if such a key exists) or the key y
D1
(otherwise).
3. For the forward-rolling delete action DŒx;
v
, a short-duration X lock is acquired
on the key x of the tuple to be deleted, and a commit-duration X lock is acquired
on the next key y of x.
4. For an undo action I
1
Œx;
v
, no lock is requested; the action is performed
under the protection of the commit-duration X lock on x acquired by T for the
corresponding forward-rolling action IŒx;
v
.
5. For an undo action D
1
Œx;
v
, no lock is requested; the action is performed under
the protection of the commit-duration X lock on the next key y of x acquired for
the corresponding forward-rolling action DŒx;
v
.
6. After completing a partial rollback with action CŒP, all locks acquired after the
corresponding set-savepoint action SŒP are released.
7. All remaining locks are released after committing or completing a total rollback
of the transaction with action C .
In (1), the S lock acquired on x for the read action RŒx;
z
;
v
is interpreted
as locking the entire key range .x
0
;x,wherex
0
is the greatest key less than x