Information Technology Reference
In-Depth Information
Consider the following simple modification of a locking protocol with lock
modes S and X. The queue of transactions that are waiting for a lock on a data item
is kept in ascending deadline order. A transaction that holds a lock but has already
missed its deadline is aborted and rolled back. If a transaction requests an S lock
on a data item currently S-locked by another transaction, the lock is not granted
immediately if there is some other transaction with an earlier deadline waiting for
an X lock on the data item; in that case the requesting transaction is put to wait for
the S lock.
What changes are needed in the design of the lock table and the locking
algorithms to implement the above-modified locking protocol? Find cases in which
the protocol works poorly.
Bibliographical Notes
Multi-granular locks already appear in the logical locking protocol applied in
System R and described by Astrahan et al. [
1976
]: locks can be acquired on granules
such as segment, relation, and tuple. System R's concurrency-control algorithm is
reviewed by Mohan [
1996a
]. The multi-granular locking protocol with lock modes
S, X, IS, IX, and SIX for tree hierarchies (Sect.
9.2
) and its generalization for
directed acyclic graphs (Problem
9.4
) come from Gray et al. [
1975
,
1976
].
The refined key-range locking protocol that uses IX locks (Problem
9.3
)isa
simplified version of the protocols presented by Mohan [
1990a
,
1996a
]. The multi-
granular locking protocol for acyclic graphs coupled with update-mode locks and
key-range locking is treated in detail by Gray and Reuter [
1993
].
The
C
OMMIT
-LSN
mechanism comes from Mohan [
1990b
,
1996b
], and its use for
improving data availability during the redo and undo passes of restart recovery is
explained by Mohan [
1993b
] (cf. Problem
9.8
). The cursor-stability isolation level
of
SQL
is discussed by several authors, including Gray and Reuter [
1993
], Berenson
et al. [
1995
], and Kifer et al. [
2006
].
Locking protocols for transactions with deadlines (see Problem
9.9
) are con-
sidered by Abbott and Garcia-Molina [
1988a
,
b
,
1989
]andAgrawaletal.[
1995
],
among others.
