COMP9315 21T1
Exercises 09
Transaction Processing: Concurrency, Recovery
DBMS Implementation
[Show with no answers] [Show with all answers]
1.
2. Consider the following transaction T1: R(X), R(X)
a. Give an example of another transaction T2 that, if run concurrently to transaction T1 without some form of concurrency control, could interfere with T1 to produce unrepeatable reads. Show the sequence of operations which would cause the problem.
[show answer]
b. Explain how the application of strict two-phase locking would prevent the problem described in your previous answer.
[show answer]
3.
4. SQL supports four isolation-levels and two access-modes, for a total of eight combinations of isolation-level and access-mode. Each combination implicitly defines a class of transactions; the following questions refer to these eight classes:
a. Describe which of the following phenomena can occur at each of the four SQL isolation levels: dirty read, unrepeatable read, phantom problem.
[show answer]
b. Why does the access mode of a transaction matter?
[show answer]
5.
6.
Draw the precedence graph for the following schedule:
T1: R(A) W(Z) C
7. T2: R(B) W(Y) C
8. T3: W(A) W(B) C
9.
[show answer]
10.
11. [Based on RG Ex.17.2] Consider the following incomplete schedule S:
T1: R(X) R(Y) W(X) W(X)
12. T2: R(Y) R(Y)
13. T3: W(Y)
14.
a. Determine (by using a precedence graph) whether the schedule is serializable
[show answer]
b. Modify S to create a complete schedule that is conflict-serializable
[show answer]
15.
16. Is the following schedule conflict serializable? Show your working.
T1: R(X) W(X) W(Z) R(Y) W(Y)
17. T2: R(Y) W(Y) R(Y) W(Y) R(X) W(X) R(V) W(V)
18.
[show answer]
19.
20. [Based on RG Ex.17.3] For each of the following schedules, state whether it is conflict-serializable and/or view-serializable. If you cannot decide whether a schedule belongs to either class, explain briefly. The actions are listed in the order they are scheduled, and prefixed with the transaction name.
a. T1:R(X) T2:R(X) T1:W(X) T2:W(X)
b. T1:W(X) T2:R(Y) T1:R(Y) T2:R(X)
c. T1:R(X) T2:R(Y) T3:W(X) T2:R(X) T1:R(Y)
d. T1:R(X) T1:R(Y) T1:W(X) T2:R(Y) T3:W(Y) T1:W(X) T2:R(Y)
e. T1:R(X) T2:W(X) T1:W(X) T3:W(X)
21.
[show answer]
22.
23. Recoverability and serializability are both important properties of concurrent transaction schedules. They are also orthogonal. Serializability requires that the schedule be equivalent to some serial ordering of the transactions. Recoverability requires that each transaction commits only after all of the transactions from which is has read data have also committed.
Using the following two transactions:
T1: W(A) W(B) C T2: W(A) R(B) C
24.
give examples of schedules that are:
a. recoverable and serializable
b. recoverable and not serializable
c. not recoverable and serializable
25. [show answer]
26.
27. ACR schedules avoid the potential cascading rollbacks that can make recoverable schedules less than desirable. Using the transactions from the previous question, give an example of an ACR schedule.
[show answer]
28.
29. Consider the following two transactions:
T1 T2
30. ———— ————
31. read(A) read(B)
32. A := 10*A+4 B := 2*B+3
33. write(A) write(B)
34. read(B) read(A)
35. B := 3*B A := 100-A
36. write(B) write(A)
37.
a. Write versions of the above two transactions that use two-phase locking.
[show answer]
b. Is there a non-serial schedule for T1 and T2 that is serializable? Why?
[show answer]
c. Can a schedule for T1 and T2 result in deadlock? If so, give an example schedule. If not, explain why not.
[show answer]
38.
39. What is the difference between quiescent and non-quiescent checkpointing? Why is quiescent checkpointing not used in practice?
[show answer]
40.
41. Consider the following sequence of undo/redo log records:
42.
Give all of the sequences of “events” that are legal according to the rules of undo/redo logging. An “event” consists of one of: writing to disk a block containing a given data item, and writing to disk an individual log record.
[show answer]
43.
44. Consider the following sequence of undo/redo log records from two transactions T and U:
45.
46.
47.
Describe the actions of the recovery manager, if there is a crash and the last log record to appear on disk is:
a.
b.
c.
d.
48. You may assume that there is an