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
