Information Technology Reference
In-Depth Information
to be X-locked for commit duration, as it is, by rule (3). Because the set of keys y
00
with y
0
y
00
z
remains the same thru LJ
2
, we conclude the lemma.
t
Lemma 6.15
Assume that a history
H
is permitted, on a given database, by the
key-range locking protocol. Then
H
contains no unrepeatable reads, except possibly
ones included in partially rolled-back action sequences.
Proof
For the sake of contradiction, assume that H contains an unrepeatable read.
By Lemmas
5.15
and
6.13
, we can write H as
H
D
˛R
1
Œx;
z
LJo
2
Œy
D
H
0
o
2
Œy ,
where x
y
z
, R
1
Œx;
z
is a read action by a transaction T
1
forward-rolling at
H
0
,ando
2
Œy is a forward-rolling insert action I
2
Œy or delete action D
2
Œy by some
transaction T
2
other than T
1
.
If T
1
has not performed a partial rollback or initialized a total rollback in H
0
that includes R
1
Œx;
z
, then, by Lemma
6.14
, T
1
holds commit-duration locks on
all keys y
00
with y
0
y
00
z
in the database at H
0
,wherey
0
is the least key with
y
0
y in that database. If o
2
Œy is an insert action I
2
Œy, y is not in the database at
H
0
,andT
2
must acquire a commit-duration X lock on y.Buttheny would be one
of the keys locked by T
1
for commit duration. On the other hand, if o
2
Œy is a delete
action D
2
Œy, y is in the database at H
0
,andT
2
must acquire a commit-duration
X lock on the key next to y at H
0
. But that next key is also among those keys locked
by T
1
for commit duration.
t
Lemmas
6.12
,
6.13
and
6.15
imply:
Theorem 6.16
Let
H
be a history of transactions in the key-range model that is
permitted, on a given database, by the key-range locking protocol. Then
H
contains
no dirty writes nor dirty reads nor any unrepeatable reads by read actions not
included in partially rolled-back action sequences.
t
6.5
Deadlocks
When using a concurrency-control scheme based on locking,
deadlocks
can occur:
in a set of transactions, each transaction is waiting for a lock to a data item locked
by some other transaction in the set, so that none of the transactions can proceed.
Example 6.17
Let T
1
and T
2
be active transactions.
1. First T
1
acquires an S lock on key x and reads the tuple with key x.
2. Then T
2
acquires an S lock on key y and reads the tuple with key y.
3. Next T
1
wants to update the tuple with key y. Therefore it requests an X lock
on y. Because of the S lock held by T
2
on y, the requested X lock cannot be
granted immediately, and so T
1
is put to sleep, waiting for T
2
to release its lock.
4. Now T
2
wants to update the tuple with key x. Therefore it requests an X lock
on x. Because of the S lock held by T
1
on x, the requested X lock cannot be
granted immediately, and so T
2
is put to sleep, waiting for T
1
to release its lock.
