CS 348: Assignment 5 for Sections 1 and 2
Spring 2020
(due by 11pm EDT on Wednesday, July 22nd)
Overview
This assignment consists of three questions. As an aid to scheduling your
work on this assignment, you should plan on spending about three hours
total on the questions. Also note that Question 2.2 is a bonus question.
Question 1.
Each of the following parts are questions on normal forms and their compu-
tation.
1. Exhibit a sequence of binary lossless join decompositions of relation
schema R/(A,B,C,D,E) that obtains a decomposition for which each
relation is in BCNF, assuming the FDs {A → BC,CD → E,B →
D,E → A} hold on R. Prove that each relation in your decomposition
is indeed in BCNF.
2. Exhibit a lossless join and dependency preserving decomposition of
relation schema R/(A,B,C,D,E, F ) by algorithm Compute3NF, as-
suming the FDs {A→ BCD,BC → DE,B → D,D → A} hold on R.
Note that this requires showing (a) a minimal cover, and (b) a proof
that one of the relations in the decomposition contains a candidate key.
Question 2.
1. Use Armstrong’s axioms to prove the soundness of the union and de-
composition rules.
1
2. (10% bonus) Prove that algorithm Compute3NF produces a lossless
join decomposition.
Question 3.
Translate each of the following SQL queries over the relational database
schema for bibliography information given on Slide 10 of Module 2 to formu-
lations in the relational algebra with multiset semantics defined in Module 10.
1. All book titles.
select distinct title
from publication, book
where publication.pubid = book.pubid
2. All publications with at least two authors.
select distinct r1.publication
from wrote r1, wrote r2
where r1.publication = r2.publication
and not r1.author = r2.author
3. All author-publication ids for all publications except books and journals.
select * from wrote
where publication not in (
(select pubid from book)
union
(select pubid from journal))
Assignment Submission
Assignment submission should be a single file uploaded to dropbox on Learn.
The file should be a pdf file that may be computer generated or a scan/photo
of a handwritten solution, as long as it is legible.
2