COMP9311 25T3: Assignment 2
Deadline: 5pm Monday Week10 (17 November 2025)
Note: Please make sure that you always use notations consistent with lecture notes. Different notations will not be accepted.
Question 1 (12 marks)
Consider a relation R (A, B, C, D, E, G, H, I, J) and its FD set F = {AB → CDI, BJ → EHI, EH → AC, I → B, HCD → AG}.
Regarding the following questions. Give and justify your answers if the question is specified.
1) Check if ABD → H. Justify your answer. (1 mark)
2) Find all the candidate keys for R. (2 mark)
3) Determine the highest normal form. of R with respect to F. Justify your answer. (2 marks)
4) Find a minimal cover Fm for F and show the steps involved. (2 marks)
5) Regarding F, does the decomposition R1 = {ACDG}, R2 = {BDEHJ}, R3 = {CDI} of R satisfy the lossless join property? Please justify your answer. (2 marks)
6) Provide a step-by-step lossless decomposition of R into BCNF normal form. (3 marks)
Question 2 (8 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 time slot.
D
Note: Each transaction begins at the time slot of its first operation and commits right after its last operation (same time slot).
Regarding the following questions. Give and justify your answers.
1) Assume a checkpoint is made between t6 and t7, what should be done to the five transactions when the crash happens between t13 and t14. (2 marks)
2) Is the transaction schedule conflict serializable? Give the full precedence graph to justify your answer. (2 marks)
3) 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 (6 marks)
Consider the following query:
P1, P2, P3, P1, P4, P1, P5, P3, P6, P2, P3, P4, P6, P2, P5
(The user is trying to read page 1 from disk, then page 2, page 3, …)
Assume there are 3 buffers in the buffer pool.
1) Sketch the process of how blocks are replaced in the Least Recently Used (LRU) policy. (1.5 marks)
2) Sketch the process of how blocks are replaced in the Most Recently Used (MRU) policy. (1.5 marks)
3) Sketch the process of how blocks are replaced in the First In First Out (FIFO) policy. (1.5 marks)
4) Among LRU, MRU and FIFO policies, which one performs better in the given query? Why? (1.5 marks)
Assignment Submission
• You are required to submit an electronic version of your answers via Moodle. While we accept handwritten submissions, please ensure they are scanned or photographed clearly to ensure legibility.
• We only accept the .pdf format. Please name your files in the following format: ass2_zID.pdf (e.g., ass2_z5000000.pdf).
Late Submission Penalty
• 5% of the total mark (26 marks) will be deducted for each additional day.
• Submissions that are more than five days late will not be marked.