University of Toronto csc343, Fall 2020
Assignment 3
Due: Thursday, December 10 before 8pm!
1. Consider a relation R with attributes ABCDEFGHI with functional dependencies S: S={AEG¡úF, B¡úAD, AG¡úHI, BG¡úD}
(a) State which of the given FDs violate BCNF.
(b) Employ the BCNF decomposition algorithm to obtain a lossless and redundancy-preventing decomposi- tion of relation R into a collection of relations that are in BCNF. Make sure it is clear which relations are in the final decomposition, and don¡¯t forget to project the dependencies onto each relation in that final decomposition. Because there are choice points in the algorithm, there may be more than one correct answer. List the final relations in alphabetical order (order the attributes alphabetically within a relation, and order the relations alphabetically).
(c) Does your schema preserve dependencies? Explain how you know that it does or does not.
(d) Use the Chase Test to show that your schema is a lossless-join decomposition. (This us guaranteed by the BCNF algorithm, but it¡¯s a good exercise.)
2. Consider a relation A with attributes LMNOPQRS and functional dependencies B. B={LNOP¡úM, M¡úNQ, NO¡úLQ, MNQ¡úLO, LMQ¡úNOS }
(a) Compute a minimal basis for T. In your final answer, put the FDs into alphabetical order. Within a single FD, this means stating an FD as XY ¡ú A, not as Y X ¡ú A. Also, list the FDs in alphabetical order ascending according to the left-hand side, then by the right-hand side. This means, WX ¡ú A comes before WXZ ¡ú A which comes before WXZ ¡ú B.
(b) Using your minimal basis from the last subquestion, compute all keys for P.
(c) Employ the 3NF synthesis algorithm to obtain a lossless and dependency-preserving decomposition of relation P into a collection of relations that are in 3NF. Do not ¡°over normalize¡±. This means that you should combine all FDs with the same left-hand side to create a single relation. If your schema includes one relation that is a subset of another, remove the smaller one.
(d) Does your schema allow redundancy? Explain how you know that it does or does not.
Show all of your steps so that we can give part marks where appropriate. There are no marks for simply a correct answer. You must justify every shortcut that you take.
What to hand in
Type your answers up using LaTeX or Word. Hand in your typed answers, in a single pdf file called A3.pdf.
Final Thoughts
Declare your group now: Well before the due date, declare your team (even if you are working solo) on MarkUs. It is impossible to do so during the late-with-penalty period.
Submission: Check that you have submitted the correct version of your files by downloading it from MarkUs; new files will not be accepted after the due date.
Some parting advice: It will be tempting to divide the assignment up with your partner. Remember that both of you probably want to answer all the questions on the final test.
1