Answer the following questions related to concurrency control and transaction
schedules. (solutions)
Consider the following transaction schedule of accesses to Amazon’s inventory
database to purchase unspecified copies of a CD, DVD, and book. Assume that the
transactions run without the benefit of isolation.
| T1 |
T2 |
| Read (# CDs) |
|
| |
Read (# Books) |
| Write (# CDs - 1) |
|
| Read (# Books) |
|
| Write (# Books - 2) |
|
| |
Write (# Books - 1) |
| |
Read (# DVDs) |
| |
Write (# DVDs - 1) |
These questions are adapted from CS 40: Database Management Systems at Furman
University (Treu 2005).
-
Explain how this schedule violates the requirement of data consistency
(i.e., what data anomaly exists?).
The transaction schedule exemplifies the lost update problem.
Transaction T2 overwrites the update to the number of books made by
transaction T1, causing the inventory to be two books more than are
actually available.
-
Write a serializable schedule for the two transactions that is not simply
serial. Justify that it is serializable and that it fixes the aforementioned
data anomaly.
| T1 |
T2 |
| Read (# CDs) |
|
| Write (# CDs - 1) |
|
| |
Read (# Books) |
| |
Write (# Books - 1) |
| Read (# Books) |
|
| Write (# Books - 2) |
|
| |
Read (# DVDs) |
| |
Write (# DVDs - 1) |
This schedule is serializable because there are no cycles in the
dependency graph between the transactions. More specifically, T2
reads the number of books before T1 writes that value, T2 writes
the number of books before T1 reads that value, and T2 writes
the number of books before T1 writes that value.
-
Add explicit locking instructions (using shared and exclusive locks) to the
initial schedule. Note that inserting locks may cause some existing
operations to be reordered. What is the outcome of the two transactions?
| T1 |
T2 |
| Shared Lock (# CDs) |
|
| Read (# CDs) |
|
| |
Shared Lock (# Books) |
| |
Read (# Books) |
| Exclusive Lock (# CDs) |
|
| Write (# CDs - 1) |
|
| Unlock (# CDs) |
|
| Shared Lock (# Books) |
|
| Read (# Books) |
|
| Exclusive Lock (# Books) fails |
|
| |
Exclusive Lock (# Books) fails |
| |
deadlock – abort transaction (and release locks) |
| Exclusive Lock (# Books) |
|
| Write (# Books - 2) |
|
| Unlock (# Books) |
|
| |
Shared Lock (# Books) |
| |
Read (# Books) |
| |
Exclusive Lock (# Books) |
| |
Write (# Books - 1) |
| |
Unlock (# Books) |
| |
Shared Lock (# DVDs) |
| |
Read (# DVDs) |
| |
Exclusive Lock (# DVDs) |
| |
Write (# DVDs - 1) |
| |
Unlock (# DVDs) |
The initial schedule deadlocks when T2 attempts to acquire an
exclusive lock on the number of books. That transaction is aborted, which
allows T1 to continue.
-
Does the transaction schedule with locking satisfy the requirements of
two-phase locking (2PL)?
No, two-phase locking (2PL) requires a transaction to have a growing
(i.e., acquiring locks) and shrinking (i.e., releasing locks) phase. In
the prior example, T1 releases its lock on the number of CDs prior to
acquiring the lock for the number of books.
-
Create a strict two-phase locking (strict 2PL) schedule for the two
transactions.
| T1 |
T2 |
| Shared Lock (# CDs) |
|
| Read (# CDs) |
|
| |
Shared Lock (# Books) |
| |
Read (# Books) |
| Exclusive Lock (# CDs) |
|
| Write (# CDs - 1) |
|
| Shared Lock (# Books) |
|
| Read (# Books) |
|
| Exclusive Lock (# Books) fails |
|
| |
Exclusive Lock (# Books) fails |
| |
deadlock – abort transaction (and release locks) |
| Exclusive Lock (# Books) |
|
| Write (# Books - 2) |
|
| Unlock (# Books) |
|
| Unlock (# CDs) |
|
| Commit |
|
| |
Shared Lock (# Books) |
| |
Read (# Books) |
| |
Exclusive Lock (# Books) |
| |
Write (# Books - 1) |
| |
Shared Lock (# DVDs) |
| |
Read (# DVDs) |
| |
Exclusive Lock (# DVDs) |
| |
Write (# DVDs - 1) |
| |
Unlock (# DVDs) |
| |
Unlock (# Books) |
| |
Commit |