EXERCISES 243
[Kaiser92] Kaiser, G., and Pu, C., “Dynamic Restructuring of Transactions,” in Database Trans-
action Models for Advanced Applications ( A. Elmagarmid, editor), Morgan Kaufmann, San
Francisco, 1992, pp. 265–295.
[Kung81] Kung, H., and Robinson, J., “On Optimistic Methods for Concurrency Control,” ACM
Transactions on Database Systems, Vol. 6, No. 2, pp. 213–226, June 1981.
[Leu91] Leu, Y., “Computing Multidatabase Applications Using Flex Transactions,” IEEE Data
Engineering Bulletin Vol. 14, No. 1, March 1991.
[Mohan86] Mohan, C., Lindsay, B., and Obermarck, R., “Transaction Management in the System
R∗ Distributed Database Management System,” ACM Transaction Database System, Vol. 11,
No. 4, pp. 378–396, 1986.
[Papadimitriou82] Papadimitriou, C., and Kanellakis, P., “On Concurrency Control by Multiple
Versions,” in Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of
Database Systems, March 1982.
[Pu93] Pu, C., and Chen, S. W., “ACID Properties Need Fast Relief: Relaxing Consistency
Using Epsilon Serializability,” in Proceedings of the Fifth International Workshop on High
Performance Transaction Systems, 1993.
[Reuter89] Reuter A., “Contracts: A Means for Extending Control Beyond Transaction Bound-
aries,” in Third International Workshop on High Performance Transaction Systems, 1989.
[Sheth92] Sheth, A., Rusinkiewics, M., and Karabatis, G., “Using Polytransactions to Man-
age Interdependent Data,” in Database Transaction Models for Advanced Applications ( A.
Elmagarmid, editor), Morgan Kaufmann, San Francisco, 1992, pp. 555–581.
[Silberschatz05] Silberschatz, A., Korth, H., and Sudarshan, S., Database System Concepts,
McGraw-Hill, New York, 2005.
[Stonebreaker77] Stonebreaker, M., and Neuhold, E., “A Distributed Version of INGRES,” in
Proceedings of the 2nd Berkeley Workshop on Distributed Data Management and Computer
Networks, Berkeley, CA, pp. 9–36, May 1977.
[Tandem87] The Tandem Database Group, “Non-stop SQL—A Distributed High Performance,
High Availability Implementation of SQL,” in Proceedings of International Workshop on
High Performance Transaction Systems, September 1987.
[Tandem88] The Tandem Performance Group, “A Benchmark of Non-stop SQL on Debit Credit
Transaction,” in Proceedings of ACM SIGMOD International Conference on Management of
Data, pp. 337–341, June 1988.
[Veijalainen92] Veijalainen, J., Eliassen, F., and Holtkamp, B., “The S-Transaction Model,” in
Database Transaction Models for Advanced Applications ( A. Elmagarmid, editor), Morgan
Kaufmann, San Francisco, 1992, pp. 467–513.
[Weikum91] Weikum, G., “Principles and Realization Strategies of Multilevel Transaction Man-
agement,” ACM Transactions on Database Systems, Vol. 16, No. 1, March 1991.
EXERCISES
Provide short (but complete) answers to the following questions.
5.1 Check the serializability of each one of the following schedules:
S1 = R1(X), R2(X), R3(X), W1(X), W3(X)
S2 = R2(X), R1(Y), W3(X), W2(X)
S3 = W1(X), R2(X), W3(X), W2(X)
244 CONTROLLING CONCURRENCY
Figure 5.31 Concurrent transactions for Exercise 5.2.
S4 = R1(X), R3(X), R2(X), W2(Y), W3(X)
S5 = R3(X), W1(X), R1(X), W2(X)
Indicate all RW, WR, and WW conflicts and show all partial commitment
orders forced by these conflicts. Indicate if the schedule is serializable. If it is,
what is the total commitment order? If it is not, indicate the first operation that
causes the problem.
5.2 Assume the following three transactions in Figure 5.31 and the order in which they
work with data items X and Y. Show three schedules that are created by applying
(A) no-locking, (B) 1PL, and (C) 2PL to these transactions. For each schedule in
(A), (B), and (C), you should show all partial commitment orders (PCOs) caused
by all RW, WR, and WW conflicts. Are these schedules serializable? If yes, what
is the serialization order? If not, why?
5.3 Assume the three transactions in Figure 5.32 and the order in which they work
with items X and Y. Answer the following for these three transactions, if we
use (A) no-locking, (B) 1PL, and (C) 2PL for concurrency control. Show the
schedules for (A), (B), and (C). Find out all partial commitment orders for RW,
WR, and WW conflicts. If the schedule is serializable, what is the serialization
order? If not, why? Are there any deadlocks?
5.4 Assume transactions T1, T2, T3, T4, and T5 generate schedules SA and SB as
shown below. (A) Are the local SA and SB schedules serializable? If so, what are
the equivalent local serial schedules? If not, why? (Show all partial commitment
Figure 5.32 Concurrent transactions for Exercise 5.3.
EXERCISES 245
orders.) (B) Are they globally serializable? If so, what is the equivalent global
serial schedule? If not, why?
SA = R1(x1), W1(x1), R2(x2), R4(x1), W2(x2), W3(x2), R4(x2)
SB = R5(x3), R1(x3), R3(x4), W2(x4), R5(x4), R3(x3)
5.5 What is the condition for the optimistic concurrency control for transactions
overlapping as (A) Ti completes its write phase before Tj starts its read phase,
(B) Ti and Tj complete their validation phase at the same time, (C) Ti completes its
validation phase before Tj completes its validation phase, (D) Ti completes its
read phase after Tj completes its validation, and (E) both Ti and Tj complete
their read phase exactly at the same time?
