Description
1 Short Questions (20 pts)
Provide a short answer (3-4 sentences at most) for each of the following questions. You may
use figures if necessary.
1. [2.5] Suppose we have a relation R as given below, representing the exam statistics for
course CS411. First project relation R to GPA (i.e., eliminate SID and Name) and
then calculate the average GPA, under the set-model and the bag-model respectively.
Which model is prefered in this example and why?
SID Name GPA
1 James 3
2 Charles 4
3 Doris 4
4 Ada 4
2. [5] Consider a relation R(A, B, C). You may assume there are no null values or duplicates in R. If the result of σY 6=V (ρR(X,Y,Z)R ./ ρR(X,V,W)R) is always guaranteed to be
empty, then what property of R can you infer? (Hint: think functional dependencies.)
3. [2.5] Consider any relation R that never contains more than one tuple. Is it true that
R must in Boyce-Codd Normal Form (BCNF)? Justify your answer
4. [4] Consider a relation R(A, B, C, D, E) with dependencies AB → CD, C → AB
D → AE, list all minimal keys for R. Also, state whether the relation R is in 3NF
with reasoning.
5. [6] Two sets of functional dependencies (FD’s) F and F
0 are equivalent if all FD’s in
F
0
follow from the ones in F, and all FD’s in F follow from the ones in F
0
. Consider
the following three sets of functional dependencies:
• F1 = A → C, B → A,
• F2 = B → AC
• F3 = AB → C, B → A
(a) Are F1 and F2 equivalent? Justify your answer.
(b) Are F1 and F3 equivalent? Justify your answer.
(c) Are F2 and F3 equivalent? Justify your answer.
3
2 Relational algebra to English (15 pts)
Consider a relation Works (name, company, salary) with no duplicates. Consider the following relational algebra expression, written in linear notation.
P1(salary) = πsalary(σcompany=“IBM”(W orks))
P2(salary) = πsalary(ρT1(s)(P1) ./s>salary P1)
P3(salary) = P1 − P2
Answer(name) = πname(W orks ./salary>s ρT2(s)(P3))
State in English what is computed as the final answer briefly. Long-winded answers will
be deducted points. For partial credit, explain what P1, P2 and P3 contain.
4
3 English to Relational Algebra (20 pts)
Consider the following relational database schema that describes information about students
and their courses. A course is uniquely identified by its CODE (e.g., “CS411”), and a student
is uniquely identified by his or her SID.
Course(CODE, units, time, room) // all courses
Student(SID, name, level) // all students, level can be “grad” or “undergrad”
Taking(SID, CODE) // current enrollment information
Write a relational algebra expression to list the information (i.e., CODE, units, time, room)
of courses that are currently offered but have no graduate students enrolled.
5
4 Data to functional dependency (20 pts)
Consider a relation R(A, B, C), satisfying some functional dependency. Two instances of R
are given as below:
A B C
2 3 1
2 2 4
A B C
2 2 1
3 3 2
4 2 1
Based on R’s schema, enumerate all possible completely nontrivial functional dependencies
(FDs) with only a single attribute on the right-hand side. Then, based on the instances
above, for each FD you listed, label whether it:
H: Definitely holds in R.
NH: Definitely does not hold in R.
CD: Cannot be determined from the information given whether or not it holds in R.
6
5 Normalization (25 Points)
Consider the following relational schema for a chain store:
Sale(clerk, store, city, date, dish, size)
// a clerk sold a dish on a particular day at a given store in a city
Menu(dish, size, price)
// prices and available size for the dish
Make the following assumptions:
• Each clerk works in one store.
• Each store is in one city.
• The price of a dish is different for different sizes. The store has standardized prices:
the same sized dish cannot be sold to two persons at two different prices.
1. Specify a set of completely nontrivial functional dependencies for relations Sale and
Menu that encodes the assumptions described above and no additional assumptions.
2. Based on your functional dependencies in part (1), specify all minimal keys for relations Sale and Menu.
3. Are the schemas of Sale and Menu in Boyce-Codd Normal Form (BCNF) according to
your answers to (1) and (2)? If not, give a decomposition into BCNF. If yes, justify
your answer.
4. Now add the following assumption:
• Each city has at most one store and each store has only one clerk.
Specify additional functional dependencies to take these new assumptions into account.
5. Based on your functional dependencies for parts (1) and (4) together, specify all minimal keys for relation Sale.
6. Are the schemas of Sale and Menu in 3NF according to your answers to (1), (4) and
(5)? If not, give a decomposition into 3NF. If yes, justify your answer.
