HW#3 --- last modified October 02 2019 23:24:25.

Solution set.

Due date: Oct 23

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:

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:

1. Exercise 3.3.2 where we replace {A,B,C,D} with {A,B,C,D,E} and add the FD {`A->D`}. Expand the BCNF violation to `A->BCD` rather than `A->BC`. Show BCNF for the original algorithm and the modification as part of your answer.
2. Exercise 3.4.1 (c) and (d).
3. Exercise 3.6.2
4. Imagine you are tasked with coming up with a Dating WebSite. Users of such a site need to be able to store profiles with say a photo. Users might swipe left or right through other user profiles and not be interested in re-seeing a profile they have previously rejected. Such a website needs to provide a way for users to message each other, etc. Given what you would expect the capabilities of such a site to be, make an E/R diagram that might be suitable for the database of such a site. Include it in your Hw3.pdf.

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.txt

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.