完成UNSW的数据库理论作业。
Assignment 2
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, F, G, H, I, J) and its FD set F = {AB → CD, C → IJ, J → DH, DI → AE, DJ → GH}.
1) Check if D → A ∈ F+. Justify your answer.
2) List all the candidate keys for R.
3) How many super keys can be found for R? Compute the total number of super keys and list 5 of them.
4) Find a minimal Fm cover for F.
5) Determine the highest normal form of R with respect to F. Justify your answer.
6) Regarding F, is the decomposition R1 = {ACE}, R2 = {BCDE}, R3 = {DJGHI} of R dependency-preserving? Please justify your answer.
7) Regarding F, is the decomposition R1 = {ACE}, R2 = {BCDE}, R3 = {DJGHI} of R lossless-join? Please justify your answer.
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.
Question 2
Consider the schedule below. Here, R(*) and W(*) stand for ‘Read’ and ‘Write’, respectively. T1, T2, T3 and T4 represent four transactions and ti represents a time slot.
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) Is the transaction schedule conflict serializable? Give the precedence graph to justify your answer.
3) Give a serial schedule of these four transactions (there can be more than 12 time slots).
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.
Question 3
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) Show the B+ tree after adding the data entry with key 5 into the original tree.
3) Show the B+ tree after deleting the data entry with key 80 from the original tree.
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).