Assignment 2
Please make sure that you always use notations consistent with lecture
notes. Different notations will not be accepted.
The deadline for assignment 2 is: Fri 21st, April 5:00 pm
Question 1 (10 marks)
Consider a relation 𝑅 (𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐺, 𝐻, 𝐼, 𝐽) and its FD set 𝐹 = {AB -> DGH, DG->EI, H->A, DEJ->CI, AI->EHJ}.
Regarding the following questions. Give and justify your answers if the question
is specified.
1) Check if DGH->J ∈ 𝐹+. (1 mark)
2) Find all the candidate keys for 𝑅. Provide the steps. (2 mark)
3) Determine the highest normal form of R with respect to F. Justify your
answer. (2 marks)
4) Regarding F, is the decomposition R1 = {ADGH}, R2 = {AEIJ}, R3 = {BCDGJ} of
𝑅 satisfy the lossless join property? Justify your answer. (2 marks)
5) 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.
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18
T1 R(B) R(A) W(B) W(A)
T2 R(A) R(C) W(A) W(C)
T3 R(D) W(D)
T4 R(C) W(C) R(B)
T5 R(D) W(D) R(A) W(A)
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 t10 and t11, what should be done to the
five transactions when the crash happens between t15 and t16. (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 (7 marks)
Consider the following query:
P1, P2, P3, P4, P5, P2, P6, P4, P7, P3, P8, P5
(The user is trying to read to read page 1 from disk, then page2, page3, …)
Assume there are 4 buffers in the buffer pool.
1) Sketch the process of how blocks are replaced in the Least Recently Used
(LRU) policy. (3 mark)
2) Sketch the process of how blocks are replaced in the Most Recently Used
(MRU) policy. (3 mark)
3) Between the LRU and MRU policies above, determine which one performs
better in the given query. Justify your answer. (1 mark)
Assignment Submission
• Students must submit an electronic copy of their answers to the above
questions to the course website in Moodle.
• Only .doc, .docx or .pdf file is accepted. The file name should be
ass2_studentID.doc, ass2_studentID.docx or ass2_studentID.pdf (e.g.,
ass2_z5100000.doc, ass2_z5100000.docx or ass2_z5100000.pdf).
Note:
1. Please do not wait until the last minute to submit. This is to prevent the
issue with the moodle submission system caused by too many students
submitting at the same time.
2. All submissions will be checked for plagiarism. The university regards
plagiarism as a form of academic misconduct and has very strict rules
regarding plagiarism. For UNSW policies, penalties, and information to
help avoid plagiarism, please see:
https://student.unsw.edu.au/plagiarism as well as the guidelines in the
online ELISE tutorials for all new UNSW students:
https://subjectguides.library.unsw.edu.au/elise
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.