C H A P T E R 1 5
C
o
n
c
u
rr
e
n
c
y
C
o
n
t
r
o
l
E
x
e
r
c
i
s
e
s
15.1 Briefly explain what is recoverability and what is cascade freedom. Mention
a protocol that ensures both properties, and explain why it ensures both the
above properties.
. .
.5
15.2 If many transactions update private items (eg. individual account balances)
15.3 Consider the following locking protocol: all items are ordered, and once an
item is unlocked, only higher numbered item may be locked. Locks may be
15.4 Mention one locking protocol which ensures that deadlocks never occur, with–
out ever aborting transactions. Give one major drawback of using the protocol.
. .
.2
15.5 Is every conflict serializable schedule potentially generatable by two-phase
locking? If not, give an example.
. .
.3
15.6
(Locking)
a. What defines the serialization order of transactions if two-phase locking is
used?
. .
.1
40 Chapter 15 Concurrency Control
15.7 (Deadlock prevention)
plain why this may be the case.
. .
.2
15.8 (TSO Protocol)
a. Outline the TSO protocol for reads
. .
.2
b. Outline the TSO protocol for writes (including the Thomas write rule)
. .
.2
+ 1
c. Outline how to modify the TSO protocol to guarantee recoverability and
cascade freedom.
. .
.2
15.9 The Oracle database implements a special concurrency control protocol for
read-only transactions, whereby a read-only transaction sees a view of the
15.10 In multigranularity locking, give the compatibility matrix for the different lock
15.11 Show that given any schedule generated by two-phase locking, the transaction
15.12 Consider the validation based concurrency control protocol you have studied
(which is also known as the optimistic concurrency control protocol). Outline
the checks that a transaction must perform during validation.
. .
.6
15.13 Consider multi-version timestamp ordering based concurrency control. Give
conditions under which a version will definitely not be used again (and can
thus be garbage collected).
. .
.4
15.14 Recall the tree locking protocol: the first lock can be on any node of the tree,
and subsequently nodes can be locked only if the parent is locked. Locking is
not required to be two phase, but still guarantees conflict serializability.
Exercises
41
15.15
Multi-version
2PL combines
features
of 2PL and
multiversion concurrency
con– trol:
updaters use locking to see the latest version of data, while read only
transactions
use old versions of data based on
timestamps.
Describe the scheme briefly. Make sure
you cover the points below, and any others that are impor- tant.
a. What are the actions of read-only transactions on
begin
/
read
/
commit?
b. What are the actions of update
transactions
on
begin
/
read
/
write
/
commit?
15.16 Suppose a set of items forms a directed acyclic graph (DAG). Show that the following
protocol assures conflict serializability.