HW#3 --- last modified January 28 2019 19:01:03..
Solution set.
Due date: Oct 19
Files to be submitted:
Hw3.zip
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:
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 ThirdNormalForm.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 each of Exercise 3.3.1 (a) and (b) add one nontrivial FD to those listed, then do the problem.
- Exercise 3.4.1 (a) and (b).
- Exercise 3.6.1. Make sure to explain why we know the tuples are in `R` to receive credit.
- Imagine you are tasked with coming up with a new Virtual Reality Movie Website. VR movies can be 180, 360 with or without 3D. People might want to
have accounts to comment on Movies. Make an E/R diagram that might be suitable for the database of such a site and include it in your Hw3.pdf.
For the coding part of your homework, you will write a program to decompose a table into 3NF relations with the lossless join and dependency preservation properties.
Your code should be based off the algorithm from class (Algorithm 3.26 in the book). The grader will compile your program from the command line with a line like:
javac ThirdNormalForm.java
The grader will then run your program with a line like:
java ThirdNormalForm 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 ThirdNormalForm test1.txt
where 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 3NF 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 separted list of
integers corresponding to one relation in the 3NF decomposition. For the example above, your program should output:
1,2,3
1,4
1,2,5
This corresponds to the relations `S(A_1, A_2, A_3)`, `T(A_1, A_4)`, `U(A_1, A_2, A_5)`, which is a 3NF lossless join and dependency preserving decomposition.
Point Breakdown
Written Part (1pt/problem |
4pts
|
ThirdNormalForm.java compiles, source code has all methods documented,
public ones in Javadocs, code text is reasonably formatted with an at most 80 column line length |
1pt
|
When run from the command line as described above, ThirdNormalForm reads in and parses into FDs the file given by the
file name supplied as a command line argument |
1pt
|
Grader can easily find in your code where you've implemented the algorithm for 3NF decomposition from class. |
1pt
|
Minimal basis for the functional dependencies computed according to algorithm from class (Step of algorithm 3.12 from book). |
1pt
|
To do the checking if an FD follows from another set of FDs calls are made to our algorithm from class for closure of a set of attributes under FDs
(Algorithm 3.7 in the book). |
1pt
|
Program outputs correct 3NF lossless join dependency preserving decompositions on all test cases |
1pt
|
Total | 10pts |
|