HW#3 --- last modified October 02 2019 23:24:25.Due date: Oct 23 Files to be submitted: Purpose: To get familiar with our BCNF and 3NF decomposition algorithms, to practice modeling using ER diagrams. Related Course Outcomes: The main course outcomes covered by this assignment are: CLO5 -- Know the algorithms for testing if a decomposition is in a given normal form and the algorithms which given a set of functional dependencies can do table decomposition into 3NF or BCNF. Specification: This homework will consists of two parts a written part which you submit in a file Hw3.pdf and a coding part BoyceCoddNormalForm.java. These files should be submitted together with a readme.txt containing your group members in the file Hw3.zip that you will submit. For the written exercises do the following problems:
For the coding part of your homework, you will write a program to decompose a table into BCNF relations with the lossless join property. Your code should be based off the algorithm from class (Algorithm 3.20 in the book). The grader will compile your program from the command line with a line like: javac BoyceCoddNormalForm.java The grader will then run your program with a line like: java BoyceCoddNormalForm some_file Here some_file is the name of a text file containing a list of functional dependencies. To be more specific the test files will consist of sequences of lines delimited by a single newline character (\n). Each line will contain a sequence of comma separated integers followed by a semicolon followed by another comma separated list of integers. As an example, the grader might type: java BoyceCoddNormalForm test1.txtwhere test1.txt is a file containing: 1,2;3 3;2 1;4 5;5 In the above, each integer `i` corresponds to an attribute `A_i`. The line `1,2;3` should be interpreted as the functional dependency: `A_1A_2 ->A_3`. If the largest integer in the file is `n`, then the relation to be split into BCNF is assumed to be `R(A_1,A_2, ..., A_n)`. For the example above, the relation to decompose would be `R(A_1,A_2,A_3,A_4,A_5)`. On such an input your program should output a sequence of lines delimited by newline characters. These lines should contain a comma separated list of integers corresponding to one relation in the BCNF decomposition. For the example above, your program should output: 2,3 1,3 1,4 1,2,5 This corresponds to the relations `S(A_2, A_3)`, `T(A_1, A_3)`, `U(A_1, A_4)`, `W(A_1, A_2, A_5)` which is a BCNF lossless join preserving decomposition.
|