Information Technology Reference
In-Depth Information
6.2
Consider applying the read-write locking protocol to the key-range transaction
model, so that for the read action RŒx;
z
;
v
the key x is S-locked for commit
duration as in key-range locking, but for the insert and delete actions IŒx;
v
and
DŒx;
v
, only the key x is X-locked for commit duration. Show that this protocol
prevents dirty writes, simple dirty reads and simple unrepeatable reads. Also show
that the
SQL
isolation level 2
ı
is achieved by keeping the S locks only for short
duration.
6.3
We apply the key-range locking protocol. What locks are acquired by the
transactions in the following histories and when are those locks released?
(a) B
1
I
1
Œ1B
2
I
2
Œ2B
3
I
3
Œ3A
2
I
1
2
Œ2C
2
C
3
I
1
Œ2.
(b) B
1
D
1
Œ0A
1
D
1
Œ0B
2
R
2
Œ0C
2
C
1
.
(c) B
1
D
1
Œ0I
1
Œ0D
1
Œ0A
1
D
1
1
1
Œ0D
1
Œ0C
1
.
Which of the histories are possible under the locking protocol? In (a), the database
is empty initially, and in (b) and (c), the database contains initially a tuple with key
value 0. If a history is possible, what is the serializability order of the transactions?
If a history is not possible under the key-range locking protocol, what isolation
anomalies does it possibly contain?
Œ0B
2
R
2
Œ0C
2
I
1
6.4
The physical structure of relation r.X;V/is a sparse (primary) B-tree indexed
by key X . With the key-range locking protocol, what locks must be acquired by the
transaction generated by the following application program fragment, assuming the
transaction is run at the serializable isolation level?
exec sql select min
.X /
1
into
:x
from
r ;
exec sql select max
.X /
C
1
into
:y
from
r ;
exec sql insert into
r
values
(
:x
,
:u
);
exec sql insert into
r
values
(
:y
,
:v
);
exec sql commit
.
6.5
The key-range locking protocol applied in Algorithms
6.6
-
6.8
ensures the
highest (i.e., serializable) isolation level for the transaction. Consider relaxing the
isolation level. How do you modify the algorithms if the transaction is only required
to run at (a)
SQL
isolation level 3
ı
,(b)
SQL
isolation level 2
ı
,or(c)
SQL
isolation
level 1
ı
.
6.6
The proof of Theorem
6.16
, stating the correctness of key-range locking,
assumes the basic key-range transaction model in which the forward-rolling update
actions are insert actions IŒx;
v
and delete actions DŒx;
v
. Modify the proof to
cover also write actions WŒx;
u
;
v
.
6.7
In Algorithms
6.6
-
6.8
, there is a (tiny) possibility that the
while
loop is iterated
indefinitely, so that the read, insert, or delete action will never be completed. In other
words, the transaction
starves
in its repeated attempts at locking the target keys and
latching the target pages. Can this problem be avoided?
6.8
Consider the extended read-write transaction model in which a transaction can
use the action CŒx to declare the updates on x done so far as committed before
