CSEP 545 Transaction Processing for E-Commerce, Winter 2005                       University of Washington	2/22/05

Assignment 6

Preliminaries

·        Read Chapter 6, Sections 5 – 8

·        Read Chapter 4 (Queuing). If you want to read ahead, read Chapter 10 (Replication).

Problem 1

In the last example of optimistic concurrency control subsection on page 6-17 of the revised Chapter 6, it says that “the above example works only if Decrement is deferred” (second to last paragraph of the subsection). Explain what goes wrong if it executes right away instead of being deferred.

Problem 2

Consider a database consisting of one file, F. Each transaction begins by issuing a command “getlock where Q,” where Q is a qualification (i.e. a Boolean formula) that’s true for some records and false for others. The data manager processes the Getlock command by setting write locks on every record in F that satisfies Q (it sets no other locks). The data manager will only allow a transaction to read and modify records that were locked by its Getlock command (otherwise the read or modify operation returns an error). The transaction can insert a new record; the data manager write locks the new record just before inserting it. The data manager holds a transaction’s locks until it commits. Does this locking algorithm prevent phantoms? If so, give a careful argument that every execution must be serializable. If not, show a non-serializable execution.

Problem 3

Suppose a transaction sets an intention-write lock on a file and later sets a write lock on a record of the file. Is it safe for the transaction to release the intention-write lock before it commits? Why?

Problem 4

Suppose the commit list contains {1,2,3,4,6} and there are no active transactions.

a.       What is the state of the table after running the following transaction?:
TID=8: Increment the balance of account 10 by 100;
             Delete account 12;
             Insert account 13 with balance 700.
 

b.      Suppose a read-only query with TID=7 reads all the accounts. It starts executing before executing transaction 8 starts executing and finishes after transaction 8 commits (same transaction 8 as part (a)). Which versions of which rows does it read?
 

c.       After transactions 7 and 8 have finished and no other transactions are active, suppose we garbage collect all the versions that aren’t needed. Assuming transaction ids increase monotonically with respect time, what does the table look like after the garbage collection step?