Chris Pollett>
CS157a
( Print View )
Student Corner:
[Lecture Notes]
[Discussion Board]
Course Info:
[Texts & Links]
[Description]
[Course Outcomes]
[Outcomes Matrix]
[Course Schedule]
[Grading]
[Requirements/HW/Quizzes]
[Class Protocols]
[Exam Info]
[Regrades]
[University Policies]
[Announcements]
HW Assignments:
[Hw1]
[Hw2]
[Hw3]
[Hw4]
[Hw5]
[Quizzes]
Practice Exams:
[Midterm]
[Final]
|
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:
- 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.
- 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).
- Exercise 3.6.3 where you add an attribute E to relation R and do (b) and (c).
- 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
Written Part (1pt/problem) |
4pts |
ModifiedSynthesis.java compiles, source code has all methods documented,
public ones in Javadocs, code text is reasonably formatted |
1pt |
When run from the command line as described above, ModifiedSynthesis 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 3NF decomposition algorithm from class modified as described above. |
1pt |
Minimal basis for the functional dependencies computed according to algorithm from class (Can be done using algorithm 3.12 from book). |
1pt |
Step 3 of the synthesis algorithm is implemented using algorithm 3.7 from the book. |
1pt |
Program outputs correct 3NF lossless join dependency preserving decompositions on all test cases. |
1pt |
Total | 10pts |
|