HW#3 --- last modified October 26 2023 00:40:05.

Solution set.

Due date: Oct 25

Files to be submitted:
  Hw3.zip

Purpose:

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO3 -- Conduct normalization to decompose relations into 3NF or BCNF when that removes anomalies.

CLO5 -- Use SQL as a data manipulation language (DML) for querying and modifying databases

Specification:

This homework will consists of two parts a written part which you submit in a file Hw3.pdf and a coding part ModifiedSynthesis.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.1 (a), (b) (1/2pt each) but where we add an attribute E to the relation and a functional dependency `E->A` to the list of functional dependencies. For part (ii) your decompositions should follow the algorithm from class to receive credit.
2. Exercise 3.4.1 where you change the third set of attributes from {A, C, E} to {A, D,E} then do (a) and (b).
3. Exercise 3.6.3 where you add an attribute E to relation R and do (b) and (c).
4. If you take a full cup of water and pour out half, is it now half-full or half-empty? If it was half-full, you are tasked with a making a social media site honor.com which is supposed to let members share people who have been helpful to them and maybe if someone has been helpful to many give them a gift or something. If it was half-empty, you are tasked with making a social media site hinder.com, where members can share people who have crossed them so that they can be collectively remembered and paid back in the negative sense. Such sites need a way to track members, to track helpers or hinderers, a way to share between members these helpers or hinderers, etc. Give 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. We will continue this developing this site in Hw4 and Hw5 as a larger scale project.

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) with the following modifications:

• Step 2 of the algorithm should be changed to:
  Partition the the functional dependencies in `G` according to their left hand sides (so two dependencies `X -> A` and `X->B` with the same left hand sides will be in the same partition). Merge each partition into a single FD using the combining rule (so `X -> A` and `X->B` would become `X->AB`). For each rule `X->Y` that results from merging the rules of a partition, use `XY` as the schema of one of the relations in the decomposition.
• We also add a Step 4 where if the set of the attributes of one table in the decomposition is a subset of the attributes of a different output table it should be deleted from the decomposition.

The grader will compile your program from the command line with a line like:

javac ModifiedSynthesis.java

The grader will then run your program with a line like:

java ModifiedSynthesis 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 ModifiedSynthesis test1.txt

where test1.txt is a file containing:

1,2;3
3;2
3;6
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_1 A_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,A_6)`. 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 3NF decomposition. For the example above, your program should output:

1,2,3
3,2,6
1,4
1,2,5

This corresponds to the relations `S(A_1,A_2,A_3)`, `T(A_3, A_6)`, `U(A_1, A_4)`, `V(A_1,A_2,A_5)`, which is a 3NF lossless join and dependency preserving decomposition.

As a second example, on a test file:

1,2;3,4
2;5

your program should output:

1,2,3,4
2,5

As a last example, on

1,2;3
1,2;4
1,2;5
3;2

your program should output:

1,2,3,4,5