This is a team assignment.
Submit your work to this assignment in a file called decompose.py.
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)
The algorithm you use will be an interative algorithm that finds a functional dependency, then uses that dependency to decompose a relation. To help the grader: at each iteration, display the relation you are decomposing, the functional dependency being used, and the two new relations that result. You should then finally show a list of relations.
3. (Optional, just for fun and not for grading): 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.