Please read through this page entirely and carefully before beginning your work.
For this homework, you are asked to implement two of the normalization algorithms outlined in the textbook.
Implement the 3NF synthesis algorithm in Figure 8.12 (page 352) of the textbook, including the part where redundant relations are removed. Note that this requires an implementation of the canonical cover algorithm, which in turn requires an implementation of the attribute closure algorithm. Nowhere in your implementation should you be computing F+, the closure of a set F of functional dependencies.
Your algorithm should read in a text file (the file name will be supplied on the Unix command line) describing a set of functional dependencies among attributes in a single table. It should compute a 3NF decomposition of this table and output a list of new tables, with their corresponding attribute sets, that make up the decomposed database.
Implement the BCNF testing algorithm informally described at the bottom of page 349. As before, you should not be computing F+ for any set of functional dependencies.
Combine your algorithm with the previous one, so that it tests the decomposition output by the 3NF algorithm and reports whether or not it is in BCNF. If it is not in BCNF, this algorithm should output the name of a table and a functional dependency that causes a BCNF violation in that table.
left_1 left_2 ... left_m -> right_1 right_2 ... right_n
Table i: attrib_1 attrib_2 ... attrib_k
The above decomposition is in BCNF.
The above decomposition has a BCNF violation in Table i: left_1 left_2 ... left_p -> right_1 right_2 ... right_q
// Functional dependencies for class scheduling database // Based on the example on page 351 course_id -> title dept_name credits building room_num -> capacity // Each term, course sections must be scheduled to avoid time/room conflicts course_id sec_id semester year -> building room_num time_slotSuppose you write your code in Python and your script is called "hw5.py". We will probably run it as follows
python hw5.py class.txtand here is one acceptable result for the run:
Table 1: course_id title dept_name credits Table 2: building room_num capacity Table 3: course_id sec_id semester year building room_num time_slot The above decomposition is in BCNF.
### This is our famous "BCNF-trouble" example prof_id -> dept_name student_id dept_name -> prof_idSuppose you write your code in Java and call the main file "Decomposition.java". We might run it like this
javac Decomposition.java java Decomposition advising.txtand here is one valid output that we could expect:
Table 1: prof_id student_id dept_name The above decomposition has a BCNF violation in Table 1: prof_id -> dept_name
Here is how we will grade the various parts of your implementation. The maximum score is 70 points.
Using the homework submission form, turn in a single zip (or tar/gzip) archive consisting of the following files: