– Part III
6
Chapter 22 Transaction Management
Review Questions
22.1 Explain what is meant by a transaction. Why are transactions important units of operation in a
DBMS?
22.2 The consistency and reliability aspects of transactions are due to the “ACIDity” properties of
transactions. Discuss each of these properties and how they relate to the concurrency control and
recovery mechanisms. Give examples to illustrate your answer.
Atomicity
22.3 Describe, with examples, the types of problem that can occur in a multi-user environment when
concurrent access to the database is allowed.
22.4 Give full details of a mechanism for concurrency control that can be used to ensure the types of
problems discussed in Question 22.3 cannot occur. Show how the mechanism prevents the
problems illustrated from occurring. Discuss how the concurrency control mechanism interacts
with the transaction mechanism.
7
22.5 Explain the concepts of serial, nonserial, and serializable schedules. State the rules for
equivalence of schedules.
Schedule A sequence of the operations by a set of concurrent transactions that preserves the
22.6 Discuss the difference between conflict serializability and view serializability.
A schedule is conflict serializable if it is (conflict) equivalent to some serial schedule (any
22.7 Discuss the types of problems that can occur with locking-based mechanisms for concurrency
control and the actions that can be taken by a DBMS to prevent them.
22.8 Why would two-phase locking not be an appropriate concurrency control scheme for indexes?
Discuss a more appropriate locking scheme for tree-based indexes.
Concurrency control for an index structure can be managed by treating each page of the index
Can use the following locking strategy:
(1) For searches, obtain shared locks on nodes starting at the root and proceeding downwards
(2) For insertions, a conservative approach would be to obtain exclusive locks on all nodes
as we descend the tree to the leaf node to be modified. This ensures that a split in the leaf
22.9 What is a timestamp? How do timestamp-based protocols for concurrency control differ from
locking based protocols?
Timestamp A unique identifier created by the DBMS that indicates the relative starting
time of a transaction.
22.10 Describe the basic timestamp ordering protocol for concurrency control. What is Thom
write rule and how does this affect the basic timestamp ordering protocol?
22.11 Describe how versions can be used to increase concurrency.
22.12 Discuss the difference between pessimistic and optimistic concurrency control?
9
22.13 Discuss the types of failure that may occur in a database environment. Explain why it is important
for a multi-user DBMS to provide a recovery mechanism.
22.14 Discuss how the log file (or journal) is a fundamental feature in any recovery mechanism. Explain
what is meant by forward and backward recovery and describe how the log file is used in forward
and backward recovery. What is the significance of the write-ahead log protocol? How do
checkpoints affect the recovery protocol?
22.15 Compare and contrast the deferred update and immediate update recovery protocols.
22.16 Discuss the following advanced transaction models:
(a) nested transactions,
Exercises
22.17 Analyze the DBMSs that you are currently using. What concurrency protocol does the DBMS
use? What type of recovery mechanism is used? What support is provided for the advanced
transaction models discussed in Section 22.4?
22.18 For each of the following schedules, state whether the schedule is serializable, conflict-
serializable, view-serializable, recoverable, and whether it avoids cascading aborts:
– Part III
10
(a) read(T1, balx), read(T2, balx), write(T1, balx), write(T2, balx), commit(T1),
commit(T2)
(b) read(T1, balx), read(T2, baly), write(T3, balx), read(T2, balx), read(T1, baly),
commit(T1), commit(T2)
(c) read(T1, balx), write(T2, balx), write(T1, balx), abort(T2), commit(T1)
(d) write(T1, balx), read(T2, balx), write(T1, balx), commit(T2), abort(T1)
(e) read(T1, balx), write(T2, balx), write(T1, balx), read(T3, balx), commit(T1),
commit(T2), commit(T3)
22.19 Draw a precedence graph for each of the schedules (a) (e) in the previous exercise.
(a) read(T1, balx), read(T2, balx), write(T1, balx), write(T2, balx), commit(T1),
commit(T2)
– Part III
11
(b) read(T1, balx), read(T2, baly), write(T3, balx), read(T2, balx), read(T1, baly),
commit(T1), commit(T2)
(c) read(T1, balx), write(T2, balx), write(T1, balx), abort(T2), commit(T1)
Without abort, get following:
(d) write(T1, balx), read(T2, balx), write(T1, balx), commit(T2), abort(T1)
(e) read(T1, balx), write(T2, balx), write(T1, balx), read(T3, balx), commit(T1),
commit(T2), commit(T3)
12
22.20 (a) Explain what is meant by the constrained write rule, and explain how to test whether a
schedule is serializable under the constrained write rule. Using the above method,
determine whether the following schedule is serializable:
(b) Would it be sensible to produce a concurrency control algorithm based on
serializability? Give justification for your answer. How is serializability used in
standard concurrency control algorithms?
22.21 (a) Discuss how you would test for view serializability using a labeled precedence graph.
Discussed in Section 22
(b) Using the above method, determine whether the following schedules are view serializable:
– Part III
13
22.22 Produce a wait-for-graph for the following transaction scenario and determine whether deadlock
exists.
T
T
4
T
5
T
7
T
2
T
3
T
6
14
22.23 Write an algorithm for shared and exclusive locking. How does granularity affect this algorithm?
read_lock(X):
write_lock (X):
B: if LOCK (X) = “unlocked”
unlock_item (X):
if LOCK (X) = “write-locked”
Algorithm 1 Locking and unlocking operations for two-mode (read-write or
15
22.24 Write an algorithm that checks whether the concurrently executing transactions are in deadlock.
Boolean function deadlock_detection
Input: A table called WaitForTable containing
transactionId; dataItemLocked; dataItemWaitingFor
Output: Boolean flag indicating whether system is deadlocked.
begin
deadlock = FALSE;
end
22.25 Using the sample transactions given in Examples 20.1, 20.2, and 20.3, show how timestamping
could be used to produce serializable schedules.
Example 22.1 would have to abort T1 when it tries to perform the write operation, roll it
16
22.26 Figure 22.22 gives a Venn diagram showing the relationships between conflict serializability,
view serializability, two-phase locking, and timestamping. Extend the diagram to include
optimistic and multiversion concurrency control. Further extend the diagram to differentiate
timestamping with
All
17
22.27 Explain why stable storage cannot really be implemented. How would you simulate table
storage?
Information residing on stable storage is never lost. Theoretically, this cannot be guaranteed. To
implement an approximation of stable storage, we need to replicate information in several
If a data transfer occurs, the system must detect it and recover the block to a consistent state. To
do so, the system maintains two physical blocks for each logical database block, written as
follows:
22.28 Would it be realistic for a DBMS to dynamically maintain a wait-for-graph rather than create it
each time the deadlock detection algorithm runs? Explain your answer.