PART I.RELATIONAL DB THEORY: FUNCTIONAL DEPENDENCIES AND DECOMPOSITION 1. Consider the relational schema R(A,B,C,D) and the following set of functional dependencies: S = {A -> B, BC -> A, D -> C}. A functional dependency X->Y (e.g., BD->A) is said to "logically follow" from S if when you compute the closure X+ ({B,D}+ in this case) it contains Y (A in this case). For each of the functional dependencies X -> Y below indicate whether it logically follows from S. If your answer is "yes", you should compute X+ showing that it contains Y. Otherwise, the answer is "no", and there must be an instance for relation R that satisfies S but does not satisfy X -> Y; find (smallest) such instance: (i) A -> C (ii) BD -> A (iii) CD -> A (iv) BCD -> A 2.Consider a relation R(A,B,C,D,E) satisfying the following dependencies: A->B, BC->E,ED->A. (a) List all keys for R. (b) Is R in 3NF? Justify your answer. (c) R is not in BCNF. Explain why? (d) Show the first step in a BCNF decomposition of R, including computing the projection of the dependencies onto the decomposed relations, and identifying keys for each subrelation. (e) Is the above decomposition lossless? Is it dependency-preserving? Are the subrelations in BCNF? 3NF? Explain each of your answers BRIEFLY. (f) Repeat step (d), if necessary, till you have decomposed R into BCNF relations. (g**) Argue whether there is a decomposition that preserves dependencies. PART II. FIX-POINT EVALUATION OF DATALOG We never had an assignment on this material. Please read https://www.cs.rutgers.edu/~borgida/cs336/dlog.recurse.eval.18.pdf and if you wish Sakai>Resources>6. Datalog Evaluation PROBLEMS: Consider the following set R of Datalog facts and rules, where b is a base predicate. b(5,3). b(3,1). m(A,B):- b(A,B). s(A,B):- m(A,1), m(B,1). s(A,B):- m(B,A). We will be considering the "fixed-point" algorithm for evaluating Datalog that computes all atomics facts that can be derived by the above Datalog program (where therefore S0={ b(5,3), b(3,1) } and R is the set of 3 rules above. To make answers easier to write and grade please represent facts, like the ones in S0, using a simple table notation: b ----- 5 3 3 1 [Aside: in all but part e) use the ("naive") algorithm introduced at the beginning, which produces duplicates, and eliminates them.] a) Use the algorithm presented in lecture (the until-loop) to compute the set of all atomic facts that can be derived by the above program, showing S1 := S0 U Infer(S0,R) S2 := S1 U Infer(S1,R) ... Please use the same notation as in lecture, so we can see what new facts are added in each Infer(S{i},R) Please show ALL tuples being added at each step, and then cross out duplicates before going on to the next step. [If you are using ASCii, you can indicate crossing out a duplicate p(1,2) say by writing p ---- ... 1 2 ... ~1~~2~ ... b) What are the answers to the Datalog query ?- m(X,3), based on your results from part (a) c) Now *add* the following two rules to R above, to get the set of rules R2: s(A,B):- s(A,3), m(3,B). m(A,B):- m(B,A). Repeat the steps in part (a), but with the new set of rules R2. d) Repeat step (a) for R2 instead of R, but using the so-called "seminaive" evaluation algorithm discussed at the end of the lecture notes (also discussed in the textbook in Section 24.5.1)