Requirement

Please make sure that you always use notations consistent with lecture notes. Different notations will not be accepted.

Question 1

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 . Show your intermediate steps.
2. Determine the highest normal form of R with respect to F. Justify your answer.
4. Regarding F, does the decomposition R1 = {ABDE}, R2 = {CGHJ}, R3 = {DGI} of satisfy the lossless join property? Please justify your answer.
5. Provide a step-by-step lossless decomposition of R into BCNF normal form.

Question 2

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 time slot.

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

1. Is the transaction schedule conflict serializable? Give the precedence graph to justify your answer.
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.

Question 3

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.

2. Given the following 3 tables,
For the following query:

List all the possible join orders. Which one performs the best? Justify your answer.

Assignment Submission

• Students must submit an electronic copy of their answers to the above questions to the course website in Moodle.
• Only .doc or .pdf file is accepted. The file name should be ass2_studentID.doc or ass2_studentID.pdf (e.g., ass2_z5100000.doc or ass2_z5100000.pdf).

Late Submission Penalty

• 5% of the max assessment mark will be deducted for each additional day (24hr) after the specified submission time and date.
• Submissions that are more than five days late will not be marked.