Question 1 (11 marks)

Consider a relation R (A, B, C, D, E, G, H, I, J) and its FD set F = {ACI -> DEJ, BE->AG, CJ->BH, DG->CI, H->D}

Regarding the following questions. Give and justify your answers if the question is specified.

1)  Find all the candidate keys for  R. Show your intermediate steps. (2 mark)

2)  Determine the highest normal form of R with respect to F. Justify your answer. (2 marks)

3)  Find a minimal cover  Fm    for  F. Justify your answer. (2 marks)

4)  Regarding F, does the decomposition R1 = {ABDE}, R2 = {CGHJ}, R3 = {DGI} of R satisfy the lossless join property? Please justify your answer. (2 marks)

5)  Provide a step-by-step lossless decomposition of R into BCNF normal form. (3 marks)

Question 2 (6 marks)

Consider the schedule below. Here, R(*) and W(*) stand for ‘Read’ and ‘Write’, respectively. T1, T2, T3, T4 and T5 represent five transactions and ti  represents a timeslot.

Each transaction begins at the timeslot of its first operation and commits right after its last operation (same timeslot).

Regarding the following questions. Give and justify your answers.

1)  Is the transaction schedule conflict serializable? Give the precedence graph to justify your answer. (2 marks)

2)  Construct a schedule (which is different from above) of these five transactions which causes deadlock when using two-phase locking protocol. You should clearly indicate all the locks and the corresponding unlocks in your schedule. If no such schedule exists, explain why. (4 marks)

Question 3 (8 marks)

1)  Consider the following query:

P1, P2, P3, P2, P4, P5, P1, P6, P3, P7, P2, P3

(The user is trying to read page 1 from disk, then page 2, page 3, …) Assume there are 3 buffers in the buffer pool.

Among Mostly Recently Used (MRU), Least Recently Used(LRU) and First in   First out(FIFO), which one performs the best in the given query? Justify your answer. (4 marks)

2)  Given the following 3 tables,

For the following query:

Select * from Department

join Project on Department.Did = Project.Did

join Manager on Department.Mid = Manager.Mid;

List all the possible join orders. Which one performs the best? Justify your answer. (4 marks)