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 16, Apr 5:00 pm
Question 1 (16 marks)
Consider a relation 𝑅(𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐺, 𝐻, 𝐼, 𝐽) and its FD set 𝐹 = {𝐴𝐵 → 𝐶𝐷, 𝐶 → 𝐼𝐽, 𝐽 →
𝐷𝐻, 𝐷𝐼 → 𝐴𝐸, 𝐷𝐽 → 𝐺𝐻}.
1) Check if 𝐷 → 𝐴 ∈ F+. Justify your answer. (2 mark)
2) List all the candidate keys for 𝑅. (2 marks)
3) How many super keys can be found for R? Compute the total number of super keys and
list 5 of them. (2 marks)
4) Find a minimal cover 𝐹𝑚 for 𝐹. (2 marks)
5) Determine the highest normal form of 𝑅 with respect to 𝐹. Justify your answer. (2 marks)
6) Regarding F, is the decomposition R1 = {𝐴𝐶𝐸}, R2 = {𝐵𝐶𝐷𝐸}, R3 = {𝐷𝐽𝐺𝐻𝐼} of 𝑅
dependency-preserving? Please justify your answer. (2 marks)
7) Regarding F, is the decomposition R1 = {𝐴𝐶𝐸}, R2 = {𝐵𝐶𝐷𝐸}, R3 = {𝐷𝐽𝐺𝐻𝐼} of 𝑅
lossless-join? Please justify your answer. (2 marks)
8) Decompose it into a collection of BCNF relations if it is not in BCNF. Make sure your
decomposition is lossless-join and briefly justify your answers. (2 marks)
Question 2 (8 marks)
Consider the schedule below. Here, R(*) and W(*) stand for ‘Read’ and ‘Write’, respectively.
, , and represent four transactions and ti represents a time slot.
Time t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12
R(B) R(A) W(B) W(A)
R(B) R(A) W(B) R(A) W(A)
R(B) W(B)
R(A) W(A) R(B) W(B)
Each transaction begins at the time slot of its first Read and commits right after its last Write
(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 four
transactions when the crash happens between t9 and t10. (2 marks)
2) Is the transaction schedule conflict serializable? Give the precedence graph to justify your
answer. (2 marks)
3) Give a serial schedule of these four transactions (there can be more than 12 time slots).
(2 marks)
4) Construct a schedule (which is different from above) of these four transactions which
causes deadlock when using two-phase locking protocol. If no such schedule exists,
explain why. (2 marks)
Question 3 (6 marks)
1) There are currently 20 records in this tree. How many additional records could be added
to this tree without changing its height (give the maximum possible number)? Justify
your answers. (2 marks)
2) Show the B+ tree after adding the data entry with key 5 into the original tree. (2 marks)
3) Show the B+ tree after deleting the data entry with key 80 from the original tree. (2
marks)
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 ass1_studentID.doc or
ass1_studentID.pdf (e.g., ass2_z5100000.doc or ass2_z5100000.pdf).
Note:
1. For any problems in submissions, please email to comp9311unsw@gmail.com
2. All submissions will be checked for plagiarism.
3. We do not accept e-mail submissions.
Warning: Before submission, please keep a copy in your university account or other reliable
cloud servers (such as dropbox or google drive). If you are not sure how, please have a look at
taggi. Usually, the submission should be successful. In case it fails, we do not accept backups
from your own computers as the modification time can be edited.
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
0 mark.
mailto:comp9311unsw@gmail.com
https://taggi.cse.unsw.edu.au/FAQ/Accessing_Your_Files/
https://student.unsw.edu.au/plagiarism
https://subjectguides.library.unsw.edu.au/elise
Assignment 2