Exercise 1
Consider the following histories:
H1=r1[x]r2[y]w1[y]r3[z]w3[z]r2[x]w2[z]w1[x]c1c2c3
H2=r3[z]w3[z]r2[y]r2[x]w2[z]r1[x]w1[y]w1[x]c3c2c1
Compute the RF (reads-from) and LRF(live read-from) relations in each history. Are these histories final state equivalent and/or view equivalent.
Exercise 2
Consider the following history:
H=r1[x]r3[x]w3[y]w2[x]r4[y]c2w4[x]c4r5[x]c3w5[z]c5w1[z]c1
Into which of the classes FSR, VSR, and CSR does this history corresponds to?
Exercise 3
Suppose you extend the model of the transactions I presented in the
class as follows. Operation value := read(x) is modeled as r[x, v]
and operation write(x,value) is modeled as w[x,v].
For this modified model, define the following:
Also, relate the class of serializable executions in this model with the conflict serializable class (CSR). That is, show that the new class is a superset of, subset of, or incomparable to CSR.
Exercise 4
Consider H=r1[x]w1[x]r2[x]r2[y]w2[y]c2w1[y]c1. Show that H is FSR but not VSR.
Exercise 5
Let H=r1[z]r3[x]r2[z]w1[z]w1[y]c1w2[y]w2[u]c2w3[y]c3. Show that H is VSR but not
CSR.
Exercise 6
Prove that if two histories are conflict equivalent then their serialization graphs are identical.
The converse is obviously not true. For example, the histories w1[x]w2[x] and w1[y]w2[y] have the same serialization graph but are clearly not conflict equivalent. Is the following, stronger version of the converse true: If histories H and H' are over the same set of transactions, have the same operations, and have the same serialization graph, then H is conflict equivalent to H'.
Exercise 7
Two transactions are not interleaved if every operation of one transaction precedes every operation of the other. Give an example of a conflict serializable history H that has the following properties: (a) transaction Ti and Tj are not interleaved in H; (b) Ti precedes Tj in H; and (c) in any serial history equivalence to H, Tj precedes Ti.
Exercise 8
Prove that every history H having the following property is conflict serializable: if operations pi and qj are conflicting operations in H, then the corresponding transactions Ti and Tj are not interleaved in H.
Exercise 9
A blind write is a write on some object x by a transaction that did not previously read x. Suppose we insist that transactions have no blind writes. Formally this means that if wi[x] in Ti then there must be a read operation ri[x] in Ti that was ordered before wi[x] in Ti.
Prove that under this assumption a history is view serializable if and only if it is conflict serializable.
Exercise 10 (HARD)
Prove Theorem 3.4 of your text-book, i.e., show that VSR and FSR coincide in the absence of dead steps.
Last modified April 4, 2011 by Divy Agrawal (agrawal@cs.ucsb.edu).