CSC549 Advanced Database Systems

Final Examination

Answer ALL questions.

  1. (16 points) Which of the following schedules are conflict equivalent ?

S1 = W2(x), W1(x), R3(x), R1(x) , W2(y), R3(y), R3(z), R2(z)

S2 = R3(z), R3(y), W2(y), R2(z) , W1(x), R3(x), W2(x), R1(x)

S3 = R3(z), W2(x), W2(y), R1(x) , R3(x), R2(z), R3(y), W1(x)

S4 = R2(z), W2(x), W2(y), W1(x), R1(x), R3(x), R3(z), R3(y)

Note that Wj(d) denotes transaction Tj performs a write on data item d, and Rk(e) denotes Tk performs a read on data item e.

  1. (17 points) The following figure shows a schedule of four transactions T1, T2, T3 and T4.

Suppose the timestamp-ordering concurrency control is used. Which, if any, of the four transactions in the above figure abort on the assumption that the timestamps of T1 through T4 are respectively

(a) 300, 310, 320 and 330

(b)250, 200, 210 and 275

In each case, what are the final read times (R-timestamps) and write times
(W-timestamps)of data items A, B and C. Assume that their initial read and write timestamps are 0 and that an aborted transaction is not restarted.

3. (15 points) Consider the three transactions T1, T2 and T3, and the schedules S1 and S2 given below. Draw the precedence graphs for S1 and S2 and state whether each schedule is serializable or not. If a schedule is serializable, write down the equivalent serial schedule(s).

T1 : R1(x), R1(z), W1(x)

T2 : R2(z), R2(y), W2(z), W2(y)

T3 : R3(x), R3(y), W3(y)

S1 = R1(x), R2(z), R1(z), R3(x), R3(y), W1(x), W3(y), R2(y), W2(z), W2(y)

S2 = R1(x), R2(z), R3(x), R1(z) , R2(y), R3(y), W1(x), W2(z), W3(y), W2(y)

4.(17 points) Suppose there are two transactions T1 and T2 with their operations coming in the following order:

T1: R1(x) W1(x) R1(y) W1(y)

T2: R2(y) W2(y) W2(x)

(That is, T1 starts with a read on x, followed by a read on y by T2, followed by a write on y by T2 and etc )

Indicate whether a deadlock or abort will occur if the concurrency control protocol used is:

(a)two phase locking, (b) strict two phase locking, (c) timestamp-ordering,

(d) wait-die, or (e) wound-wait.

Explain your answers.

  1. (10 points) The prime objective of index is to speed up the processing of queries by allowing fast access to data in table. However, in some situation, using the index of a table actually results in longer processing time. Give an example of such a situation. Explain your answer.
  1. (10 points) If you were the designer of a database system, would you choose the deferred update scheme or the immediate update scheme? Give your reason(s).
  1. (15 points) Let R and S be two tables, and A and B the attributes of R and S respectively. Consider the join of two tables R and S, the join condition being R.A = S.B. The following is a nested loop algorithm to process this join, with R in the outer loop.

For each row r in R,

for each row s in S,

if r[A] = s[B], then return <r, s>

Suppose table R has m blocks and table S has n blocks. For the processing of the above nested loop algorithm, assume that a buffer with only 2 blocks is allocated. Thus, only one buffer block can be used for the rows of R and one buffer block for the rows of S.

(a)Determine the number of disk I/Os for the above nested loop algorithm.

(b) What is the number of disk I/Os if table S is in the outer loop ( R in the inner loop)?

(c) Assume that 1 < m < n. (i.e., R is a smaller table). If the buffer has a capacity of 3 blocks, how many blocks would you assign for rows of R that would minimize the number of disk I/Os using the nested loop algorithm ?

1