Information Technology Reference
In-Depth Information
How is the multi-granular locking protocol generalized from trees to acyclic
graphs? Consider what nodes on the paths from the root unit down to the target
unit need to be locked (a) for reading the target unit and (b) for updating the target
unit.
Assuming that there is a sparse B-tree index to relation r.
X
;Y;V/on the primary
key X and a dense B-tree index to r on the attribute Y , what locks are acquired for
the following transactions under index-specific multi-granular key-range locking?
T
1
W
select
X , V
from
r
where
Y
D
y
0
;
commit
.
T
2
W
insert into
r
values
.x; y;
v
/;
commit
.
9.5
Assuming a multi-granular locking protocol with a three-level granule hierar-
chy (database, relations, tuples), what locks are acquired for the actions generated
from the following application program fragment when the transaction is run (a) at
the serializable isolation level and (b) at cursor stability?
exec sql declare cursor
C
for
select
from
r
where
:y
<X
and
X<
:z
for update
exec sql open
C
while
sqlstate
D
OK
do
exec sql fetch
C
into
:x
,
:v
if
f.
:v
/
then
update
r
set
V
D
g.
:v
/
where current of
C
end if
end while
exec sql close
C
exec sql commit
Here f and g are some functions on the domain of attribute V of relation r.
X
;V/.
9.6
Define a locking protocol that is a combination of multi-granular key-range
locking and update-mode locking. Give both the lock-compatibility and lock-
upgrade matrices. Apply the protocol to the transaction of the previous problem.
9.7
Reconsider Problem
6.7
regarding the starvation problem present in Algo-
rithms
6.6
-
6.8
. Assume that the algorithms are used to read, insert, and delete tuples
in relation r . Show how the multi-granular locking protocol can be used to prevent
starvation. To that end, work out simple modifications to the algorithms.
9.8
In Sect.
9.7
we explained how the
C
OMMIT
-LSN
mechanism makes it possible to
accept new transactions to the system while the undo pass of restart recovery is still
in progress. Actually, using the same mechanism, we can in some cases run new
transactions already during the redo pass. Explain how.
9.9
A
real-time database system
processes transactions with time constraints such
as
deadlines
. The system tries to minimize the number of transactions that miss their
deadlines. To that end, the locking protocols should be modified so as to observe the
deadlines of transactions.
