$23.99
Assignment #2 Solution
General Instructions
• Feel free to talk to other members of the class in doing the homework. You should, however, write down your solutions yourself. List the names of everyone you worked with at the top of your submission.
• Keep your solutions brief and clear.
• Please use Piazza if you have questions about the homework but do not post answers.
Feel free to use private posts or come to the office hours.
Homework Submission
• We DO NOT accept late homework submissions.
• We will be using Compass for collecting the homework assignments. Please submit your answers via Compass. Hard copies are not accepted.
• Contact the TAs if you are having technical difficulties in submitting the assignment;
attempt to submit well in advance of the due date/time.
• The homework must be submitted in pdf format. Scanned handwritten and/or hand- drawn pictures in your documents won’t be accepted.
• Please do not zip the answer document (PDF) so that the graders can read it directly on Compass. You need to submit one answer document, named as hw2 netid.pdf.
• Please see the assignments page for more details. In particular, we will be announcing clarifications, if any, on this page.
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
2
3
4
James
Charles Doris Ada
3
4
4
4
2. [5] Consider a relation R(A, B, C ). You may assume there are no null values or dupli- cates in R. If the result of σY =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 → C D, 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:
•
F 1 = A → C, B → A,
•
F 2 = B → AC
•
F 3 = AB → C, B → A
(a) (b) (c)
Are F 1 and F 2 equivalent? Are F 1 and F 3 equivalent? Are F 2 and F 3 equivalent?
Justify your answer. Justify your answer. Justify your answer.
2 Relational algebra to English (15 pts)
Consider a relation Works (name, company, salary) with no duplicates. Consider the follow- ing relational algebra expression, written in linear notation.
P 1(salary) = πsalary (σcompany=“I BM ”(W orks)) P 2(salary) = πsalary (ρT 1(s) (P 1) ./ssalary P 1) P 3(salary) = P 1 − P 2
Answer(name) = πname (W orks ./salarys ρT 2(s)(P 3))
State in English what is computed as the final answer briefly. Long-winded answers will be deducted points. For partial credit, explain what P 1, P 2 and P 3 contain.
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.
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
2
3
2
1
4
A
B
C
2
3
4
2
1
3 2
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.
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 rela- tions 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 ac- count.
5. Based on your functional dependencies for parts (1) and (4) together, specify all min- imal 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.
