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:
Exercise 3
Recall the variants of 2PL:
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).