1.1. select c1, ..., cn from R where p or q

1.2. union(project(select(R, p), c1, ..., cn),
           project(select(R, q), c1, ..., cn))

1.3. union(select(R, p), select(R, q)) = select(R, p or q)

1.4. project(select(R, p or q), c1, ..., cn)

1.5. The rewritten plan (using or instead of union) is preferable,
since it does one scan instead of 2, and avoids the need for duplicate
elimination.



2.1. join(join(S, U), T)

2.2. join(S, U), because of the sequential scan of S.

2.3. Add an index on S(uid). 

2.4. The hash join would probably be replaced by a nested loop join in
which select(U, f = 1) is the outer loop. Then on the inner loop, we
locate S rows via the index on uid.

2.5. create index on S(uid, c, d), or create index on T(tid, e)



3.1. A = 10, B = 20, C = 30, X does not exist. I.e., the state that
existed at the beginning of the transaction.

3.2. A = 10, B = 20, C = 30, X = 40. RR means the repeated reads yield
the same values. RR does not protect against phantoms, so X is now
visible.

3.3. A = 12, B = 10, C does not exist, X = 40, because all of these
were committed before the second set of reads by T1.



4.1. A = 22, B = 23, C = 36, D = 34

4.2. A = 21, B = 26, C = 32, D = 42



5.1. 30

5.2. Because T1 has already written A, and has not committed. Both
writes cannot succeed, so T3 has to wait to see what T1 does. If it
commits, T3 will fail on commit. If T1 rolls back, then T3 can commit.

5.3. When T1 commits.

5.4. It either fails immediately, or continues to run and then fails
on commit. (Either answer acceptable.)

5.5. The original value of A is visible to T1, T2, T3 and T4, but not
T5 or T6. That version is obsolete once T1, T2, T3 and T4 have all
finished execution.

5.6. The original value of B is visible to T2, T4. This version
becomes obsolete once these transactions finish execution. (Note that
T1 writes B but never reads it.)

5.7. The original value of C is visible to T1, T2. This version
becomes obsolete once these transactions finish execution.

5.8. T6 reads the version of A that was current when it began. That
could be T1 or T2. (T3 hasn't committed, T4 and T5 commit later). Of
T1 and T2, only T1 writes A, setting it to 11. So T6 sees the value of
11.



6.1. Committed transactions must not be undone. T1 and T2 have
committed by time 26. T3 has aborted (time 18) before it's change to C
was written to the database. The undo algorithm would undo update(T3,
c, 30) (i.e. set c to 30), although this is unnecessary.

6.2. Now T1 is not committed, so its actions need to be undone:
update(T1, c, 30), update(T1, b, 25), update(T1, a, 10).

6.3. Same as 6.2.

6.4. A was output before the log was flushed. A crash between the two
steps would leave A updated, WITHOUT the undo action in the log,
resulting in a corrupt database. However, we will get lucky in this
case and not corrupt the database because A wasn't updated between the
flushes at times 23 and 8.

6.5. Simply restart the recovery process. Repeating undos is harmless.