NEW MEXICO STATE UNIVERSITY
Department of Computer Science

Databases Qualifying Examination
August 23rd, 1999 -- 1-3pm

1. [15 points] Suppose that you have entity sets ADVISOR and STUDENT. Explain how you can use functional dependencies to specify that there exists a m-1 relationship from students to advisors.

Answer: $STUDENTS \rightarrow ADVISOR$

2. [30 points] a) Assume that we have a relation scheme R=(A,B,C) and that the domains for A, B, and C have n, m, and l elements, respectively. How many relations defined on R can we have? b) Suppose R is a relation with attributes $A_1,A_2,\ldots,A_n$. As a function of n, tell how many superkeys R has if the only key is A₁.

Answers: a) $2 ^{n \times m \times l}$. b) All the subsets of R that contain A₁: 2 ^n-1

3. [40 points] Consider the relation scheme R = (C, T, H, R, S, G), the set of functional dependencies $F = \{ C \rightarrow T, CS \rightarrow G, HR \rightarrow C, HT \rightarrow R, HS \rightarrow R \}$, and the decomposition $\rho = \{ CSG, CT, CHR, CHS \}$. a) Prove that the functional dependency $HT \rightarrow R$is not preserved by the decomposition. b) Prove that the decomposition is lossless with respect to F. c) Prove that the decomposition is in 3NF with respect to F.

Answers: a) The following relation defined on CTHRSGproves it: $\{ (c1, t, h, r1, s1, g1) (c2, t, h, r2, s2, g2) \}$.

b) The chase procedure can be used to prove it. c) They have to prove that the decomposition is in BCNF and then argue that BCNF implies 3NF.

4 [15 points ] Let R, S, and Tbe three ternary relations. Write a Datalog program that defines the result of the following relational algebra expression: $(R - S) \cap (R - T)$.

Answer:
ans(X,Y,Z) :- p1(X,Y,Z), p2(X,Y,Z).
$p1(X,Y,Z) : R(X,Y,Z), \neg S(X,Y,Z)$,
$p2(X,Y,Z) : R(X,Y,Z), \neg T(X,Y,Z),$