The first part of this assignment is analytical; the second is programming. You should turn in your answers to the first part of the assignment in a file named designtheory.txt; the second part should be in a file called decompose.py. You should submit to Moodle a single zip file containing both of these.
1. Consider a relation R with five attributes ABCDE. You are given the following dependencies: A -> B, BC -> E, and ED -> A. What are all of the candidate keys in R? Is R in 3NF? Is R in BCNF?
2. Suppose that you are given a relation R with four attributes ABCD. For each of the following sets of FDs identify the candidate key(s) for R, indicate whether or not R is in BCNF, and indicate whether or not it is in 3NF. If R is not in BCNF, provide a lossless decomposition such that the new relations are in BCNF.
(a) C -> D, C-> A, B -> C
(b) B -> C, D -> A
Write the following two functions below (with whatever additional code you need). There's an optional third function to write if you're looking for an extra challenge. Pseudocde for all of these is in chapter 8, so make sure to look there. In some cases, multiple versions are presented in varying levels of difficulty/efficiency.
1. Write a Python function to calculate the closure of a list of functional dependencies for a specific relation schema. Assume that a functional dependency is represented as a tuple, where each item in the tuple is a list of attributes. In order to keep everything easier to read and avoid tons of quotation marks, we'll use numbers for attributes instead of letters. For example, the functional dependency
1 2 -> 3 4 5
would be represented as ([1,2],[3,4,5]). The textbook provides a number of different algorithms for calculating the closure of a set of FDs. You do not need to be concerned about efficiency; you can choose whichever algorithm you like. If you are looking for an extra challenge, however, feel free to implement this as efficiently as you can.
Your function should specifically be called closure and should be used in the following form:
fd1 = ([1],[2]) fd2 = ([2,3],[4,5]) allfds = [fd1,fd2] print closure([1,2,3,4,5],allfds)
2. Write a function called bcnf that takes a relation schema (i.e., a list of attributes), and a list of functional dependencies as defined above, and performs a lossless decomposition of that relation into BCNF. Here is an example of how it would be used:
fd1 = ([1],[2]) fd2 = ([2,3],[4,5]) allfds = [fd1,fd2] print bcnf([1,2,3,4,5],allfds)For next time I use this assignment: As you decompose the original relation, print out the relation you are decomposing, the two new relations, and the functional dependency you are using to drive it.
3. (Optional, just for fun): write a function called thirdnf with the same specifications as above, but it decomposes the original relation into relations in third normal form such that the decomposition is both lossless-join and dependency-preserving.