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.

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₁.

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.

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)$.