Assignment 2 due April 8, Tuesday at start of class

Notation: ri(x) means a read of database item x by transaction ti
	wi(x) means a write of database item x by transaction ti
	ci means commit of transaction ti
	ai means abort of transaction ti

1. Suppose we have two transactions:

t1 = r1(x) r1(y) w1(z) w1(x)

t2 = r2(z) w2(z) r2(x) w2(y)

None of the following sequences of operations is a history. In each
case, explain how it fails to satisfy definition 3.1.

a) r1(x) r2(x) r2(z) w2(z) w2(y) c2 r1(y) w1(z) w1(x) c1

b) r1(x) r1(y) r2(z) w2(z) c2 w1(z) w1(x) c1 r2(x) w2(y)

c) r1(x) r1(y) w1(z) w1(x) a1 r2(z) w2(z) r2(x) w2(y)

d) r1(x) r1(y) w1(z) w1(x) c1 r2(z) a1 w2(z) r2(x) w2(y) a2


2. Given the following two transactions, write down all totally
ordered histories in which both transactions commit.

t1 = r1(x)
t2 = w2(x) w2(y)

3. Here is a history. What are its prefixes?

s = r1(x) c1 w2(x) w2(y) c2

4. Here is a schedule. What is trans(s), commit(s), abort(s), and active(s)?

s = r1(x) c1 w2(x) w3(y) w2(x) a2 w4(x) w4(y) r5(z) a4 c3