asg3

McMaster University SFWRENG 3DB3, Fall 2023 Assignment 3 Due: Dec. 1, 2023 at 10:00pm November 23, 2023 I. Database Design (65 marks) Question 1 (12 marks) Keys Consider a relation schema R ( A, B, C, D, E ) , and the set of functional dependencies F = { A → BC CD → E B → D E → A } Find all candidate keys (i.e., minimal keys) of relation R . Show all the steps you took to derive each key, and clearly state which of Armstrong’s axioms are used in each step. Question 2 (8 marks) Decomposition Consider the relation R(A,B,C,D,E), and the decomposition of R into R1(ABC) and R2(ADE). (a) (4 marks) Give a set of functional dependencies (FDs) such that the decomposition into R1 and R2 is lossless join and dependency preserving. Show your work and explain why your FDs satisfy the criteria. (b) (4 marks) Give a set of functional dependencies such that the decomposition into R1 and R2 is not lossless join, but dependency preserving. Show your work and explain why your FDs satisfy the criteria. Question 3 (35 marks) Functional Dependencies, BCNF The Department has a database containing information about all lectures during a term. The Schedule relation has the following schema: 1

Schedule ( C, D, T, R, P, A ) where C represents a course, D for day (weekday), T for time, R for room, P for professor, and A for head TA. The set of functional dependencies F defined over Schedule are: F = { RDT → P, RDT → C, C → A, PDT → R, PDT → C, CDT → P, CDT → R } Answer the following questions: (a) (4 marks) Is the FD RDT → AP entailed by F ? Explain and show your work with references to Armstrong’s axioms. (b) (6 marks) Find all the key(s) of relation Schedule . Show your work (i.e., how each key is derived). (c) (6 marks) Is Schedule in BCNF? If not, decompose it into smaller relations that are each in BCNF. Show your work at each step. (d) (6 marks) We can create a new relation ProfsSchedule ( D, T, P ) by projecting some at- tributes of Schedule . Are there new functional dependencies that hold over ProfsSchedule ? If so, state these FDs. If not, state why not. In both cases, show your work at each step to justify your answer. (e) (13 marks) Find a minimal cover F min for F . Show all the steps in your derivation of F min . Question 4 (10 marks) Armstrong’s Axioms Prove the following using Armstrong’s axioms (using only the axioms presented in class). Show all the steps of your proof, and indicate which of Armstrong’s axioms is applied in each step. a) (5 marks) Consider the schema R(A,B,C,D,E,F), and the following functional dependencies: A → BCD, BC → DE, B → D, D → A . Show that AF is a superkey. b) (5 marks) Given the relational schema R ( A, B, C, D, E, F ) and the FDs F 1 : { AB → C , A → D , CD → EF } . Show that AB → F . II. Transactions and Concurrency (30 marks) Question 5 (6 marks) Schedules I Consider schedules S 1 , S 2 below. State which of the following properties hold (or not) for each schedule: strict, avoids cascading aborts, recoverability. Provide a brief justification for each answer. (a) (3 marks) S 1 : R 1 ( X ); R 2 ( Z ); R 1 ( Z ); R 3 ( X ); R 3 ( Y ); W 1 ( X ); C 1 ; W 3 ( Y ); C 3 ; R 2 ( Y ); W 2 ( Z ); W 2 ( Y ); C 2 (b) (3 marks) S 2 : R 1 ( X ); R 2 ( Z ); R 3 ( X ); R 1 ( Z ); R 2 ( Y ); R 3 ( Y ); W 1 ( X ); W 2 ( Z ); W 3 ( Y ); W 2 ( Y ); C 3 ; C 1 ; C 2 2