Practice Exam Solutions (Draft)

Draft Solutions to Practice Midterm
Fall, 1999
Posted at 8:30pm, Dec. 14, 1999
Updated at 2:10pm, Dec. 15, 1999

1A.  Semantic query optimization uses constraints on the database on the
database schema to transform queries into others which are more efficient
to execute.  For example, a semantic query optimizer would automatically
return NULL for the following query if a constraint that states that books
can only be get copyrights after publication existed in the database:

select copyrightdate
from book
where copyrightdate < publicationdate;

1Ba.  Assume that joining R and S results in 5000 tuples.
Join selectivitiy =
| R*S | / | RxS | =
5000 / (20000 * 5000) = 1/20000

1Bb.  br = number of blocks for r (PRESCRIBE) = 50
      bs = number of blocks for s (BOOK) = 100
      js = join selectivity = 1/20000
      bfrRS = 50
So, the access cost is approximately
Cj1 = br + (br * bs) + ((js * |R| * |S|)/bfrRS) =
50 + (50 * 100) + (( (1/20000) * 5000 * 20000)/ 50) =
5150

1Bc.  Cj2c = br + (|R|*(xb + 1)) + ((js*|R|*|S|)/bfrRS) =
50 + (5000*(3+1)) + (((1/20000)*5000*20000)/50) =
50 + 20000 + 100 = 20150

2A.  c is serializable, equivalent to T2;T3;T1

2B.  S5 is cascadeless but not strict.  It is cascadeless because each item
     that is read is from a committed transaction.  It is not strict
     because T2 writes Y after T3 writes Y, but before T3 commits.

3Aa. 2PL requires a growing phase, then a shrinking phase.  The given
     transaction alternatively obtains and releases several locks.

3Ab. T (conservative 2PL)
     read_lock(X)
     write_lock(Y)
     read(X)
     unlock(X)
     read(Y)
     Y:=X+Y
     write(Y)
     unlock(Y)

3Ac. T (strict 2PL)
     read_lock(X)
     read(X)
     read_lock(Y)
     read(Y)
     Y:=X+Y
     write_lock(Y)
     unlock(X)
     write(Y)
     unlock(Y)

3Ba. No, because T3 logically happens after T2, and overwrites T2's value of X.

3Bb. Yes, because T4 is reading a value that was installed in the past.
     (write_TS(X) <= TS(T4)).

3Bc. read_TS(X) = t4.

3Bd. T1;T2;T3;T4

3C.
2PL              deadlock free                   recoverable
------------------------------------------------------------
basic            no                              no
conservative     yes                             no
strict           no                              yes
rigorous         no                              yes

3D.  S:r1(x);r1(y);w1(x);w1(y);c1;r2(x);r2(y);w2(x);w2(y);c2 - Not sure what
     this question wants.  At the very least, S does not deadlock, because
     T1 and T2 execute serially, so do not simultaneously contend for
     resources.

4a.  c

4b.  a

4c.  c

4d.  d