Information Technology Reference
In-Depth Information
in the database (if such a key exists) or the range .
1
;x (otherwise). Note that
x
z
x
0
.
In (2), the short-duration X lock on the next key y is released when the tuple
.x;
v
/ has been inserted into the data page, the insertion has been logged, and
the page has been unlatched. The lock is used to check that no other transaction
has locked the key range .x
0
;y,wherex
0
is the greatest key less than y in the
database before the insertion. After the insertion, the commit-duration X lock on x
is interpreted as locking the key range .x
0
;x.
In (3), the short-duration X lock on x is released when the tuple .x;
v
/ has been
deleted from the data page, the deletion has been logged, and the page has been
unlatched. The lock is used to check that no other transaction has locked the key
range .x
0
;x,wherex
0
is the greatest key less than x in the database. After the
deletion, the commit-duration X lock on the next key y is interpreted as locking the
key range .x
0
;y.
In (4) and (5) it is important to note that the undo actions indeed can be
performed under the protection of the single commit-duration X lock acquired for
the corresponding forward-rolling action, although for those forward-rolling actions
also a short-duration lock had to be acquired besides the commit-duration lock. This
is in accordance with the principle shared by all locking protocols and mentioned
above in Sect.
6.3
: the rollback of a transaction can never fail due to a deadlock.
Example 6.9
Consider the database D
Df
.1; 10/
g
and transactions
T
1
D
BR
Œx;
1;
u
RŒy; >x;
v
C
T
2
D
BR
Œx;
1;
u
I Œ2;
u
C
10C
and their history:
H
3
D
T
1
W
BR
Œ1;
1; 10
RŒ2; >1; 20C
T
2
W
BR
Œ1;
1; 10I Œ2; 20C
With the key-range locking protocol, locks are acquired and released as follows:
1. For the first R1Œ1;
1; 10, a commit-duration S lock on key 1 for T
1
.
2. For the second RŒ1;
1; 10, a commit-duration S lock on key 1 for T
2
.
3. For I Œ2; 20, a commit-duration X lock on key 2 and a short-duration X lock on
the next key
1
for T
2
.
4. After I Œ2; 20, the short-duration lock on key
1
is released.
5. After the first C , the commit-duration locks held by T
2
on keys 1 and 2 are
released.
6. For RŒ2; >1; 20, a commit-duration S lock on key 2 for T
1
.
7. After the second C , the commit-duration locks held by T
1
on keys 1 and 2 are
released.
In this case, all locks can be granted immediately in the order in which they are
requested. Thus the history H
3
is possible under the key-range locking protocol.
t
A major task in proving the correctness of key-range locking is to show that
locking the key y next to x implies that at all later points in the history the (possibly
