CMPSC 274: Homework #2

Spring 2011

Date due: Wednesday, April 27, 2011 5pm

Exercise 1
Prove that the histories produced by the basic two-phase locking protocol are Order Perserving Conflict Serializable (OPCSR), that is the order of non-interleaved transactions is preserved in the equivalent serial order of transactions.

Exercise 2
Consider the following restricted transaction model:

  • Transactions have only exclusive accesses (i.e., only update operations instead of usual read and write).
  • Transactions do not access the same object twice.
  • For any pair of transactions at run-time, they can have at most one conflicting access between them.
    • Now suppose we use a locking protocol which requires that the object accesses is indeed protected by locks but two-phase locking rule is not enforced. That is, transactions can obtain a lock after releasing a lock on another object. Does this protocol ensure serializability? If yes, give a proof of correctness otherwise give a counter-example.

    Exercise 3
    Recall the variants of 2PL:

  • Conservative 2PL (C2PL): all locks are acquired when a transactions begins execution.
  • Strict 2PL (S2PL): all write locks are held until the transaction terminates.
  • Strong 2PL (SS2PL): all read and write locks are held until the transaction terminates.
    • Your textbook asserts that the inclusion is proper, i.e., SS2PL strict-subset-of S2PL strict-subset-of 2PL. Establish this relationship by giving examples of histories (e.g., a history that is 2PL but not S2PL and so on). Also, can you say something about the relationship between C2PL and SS2PL?

    Exercise 4
    Recall the definition of COCSR (Commit Order Conflict Serializability): if pi[x] and qj[x] conflict and pi[x] is before qj[x] in the history then Transaction Ti commits before Transaction Tj. Prove that SS2PL strict-subset-of COCSR.

    Exercise 5
    Consider a distributed database in which a data-item is stored redundantly at multiple database sites. Such databases are referred to as replicated databases. For simplicity, assume that the database is fully replicated, i.e., a copy of a data-item exists at every site in the network.

    Does (fully) replicated data, in any sense, simplifies the execution of transactions in distributed databases? Argue why or why not?

    Exercise 6
    In locking and TO protocols, observe that once a transaction T completes it no longer influences the scheduling of future steps. What this means is that the scheduler does not need to maintain any information about ``completed'' transactions. The same does not hold for schedulers that are based on serialization graph testing. Give an example to illustrate the scenario where the SGT-based scheduler needs to maintain the information about completed transactions. Next, give a sufficient condition for safely discarding the completed transactions from the serialization graph.

    Exercise 7
    Consider a two-phase locking protocol with a lock table that permits at least one order-shared relationship compared to the traditional basic twophase locking protocol. Call this protocol 2PL/OS. Now show that the histories produced by basic 2PL are strictly contained in the class of histories produced by 2PL/OS. That is prove that if a history is produced by basic 2PL then it must also be produced by 2PL/OS. Then show that there exists at least one history that results from 2PL/OS but not by basic 2PL.

    Last modified April 18, 2011 by Divy Agrawal (agrawal@cs.ucsb.edu).