Homework 4 Logistics

CS 411: Database Systems

Homework 4
Logistics
1. This homework is due on July 15th at 23:59. We DO NOT accept late homework
submissions.
2. You will be using Gradescope to submit your solutions. Answer each sub-question (e.g.
“a.”) on a new page and submit your solution as a single PDF file on Gradescope. The
link for submissions on GradeScope will be updated HERE soon.
All registered students should have received an email invitation to GradeScope. Please
submit the PDF to "Homework 4".
3. *IMPORTANT*: Please make sure to link PDF pages with the corresponding question
outline on GradeScope.
4. Please write all answers electronically. We won’t grade handwritten/hand-drawn
versions. If you are looking for tools to create ER diagrams etc, consider
https://www.draw.io, GraphViz, or simply PowerPoint.
5. Please write down any intermediate steps to receive full credit.
6. Feel free to discuss homework problems with your classmates. But you should write your
own solutions. If you find yourself drawing ER diagrams on a paper/board with a
classmate, you’re going too far. List the names of everyone you worked with at the top
of your submission.
7. Keep your solutions brief and clear.
8. Please use Piazza if you have questions about the homework but do not post
answers. Feel free to use private posts or come to office hours.
Rubric
1. Always underline primary keys in ER diagrams and UML diagrams.
2. For the questions about ER and UML diagrams, address as many constraints implied in
the problem description as possible. Explicitly state any extra assumptions you make
that cannot be derived from the description.
3. When drawing ER diagrams or converting an ER diagram to a relational schema, have
the following design principles in mind:
a. Try not to create unnecessary entities
b. Try not to create tables that might suffer redundancy
Section 1. ER and UML Diagrams
Problem 1. ER Diagrams (10 pts)
Given the descriptions, draw the corresponding ER diagrams.
a. Each department belongs to a university. A university can have many departments. Each
university is uniquely identified by a university ID. Each university also has information
about the number of research programs designed in that university. Departments are
uniquely identified by the department ID and also the university ID which it belongs to.
Each department also has information about the number of professors and the number
of students in the department. (2.5 points)
b. A professor supervises students. A student can only be supervised by exactly one
professor, but one professor can supervise multiple students. Each professor is uniquely
identified by a professor ID, and also has information such as name and research area.
Each student is uniquely identified by a student ID, and also has information including
the name and age of the student. (2.5 points)
c. Customers shop at shopping malls. A Customer is uniquely identified by Customer ID,
and also has information about Customer Name. A shopping mall is uniquely identified
by its shopping mall ID, and also has information of its name. Crossgate is a specific
shopping mall and it has information about its current address and hours of operation.
(2.5 points)
d. For departments belonging to a university, each department is uniquely identified by the
department ID and the university ID and university name of the university that the
department belongs to. Each department also has information such as the department
name and the number of professors. University is uniquely identified by the university ID
and the name of the university. There are two kinds of departments: computer science
department and business department. Computer science department has information
about the number of servers, and the business department has information about
industry collaborators.(2.5 points)
Problem 2. ER Diagram & UML (20 pts)
The following requirements describe a database for maintaining information about a
Supermarket, Supermarket Suppliers, its Customers and Employees.
a. Each supermarket is uniquely identified by supermarket ID. It also has other information
including the Name and Address of the supermarket.
b. There are Supermarket Suppliers who supply groceries to exactly one supermarket.
Each Supermarket can have many Supermarket Suppliers. Each Supermarket Supplier
is uniquely identified by Supplier ID and Supermarket ID. It also has information about its
name, address.
c. One Supermarket has many Customers. Each Customer buys groceries from many
Supermarkets. The customers are uniquely identified by Customer ID. Each customer
also has information about the customer's name.
d. Each Supermarket can have many employees working for the supermarket. An
employee can work for at most one supermarket. Each supermarket also has exactly
one employee who manages the supermarket. An employee can manage at most one
supermarket.
e. The employees are uniquely identified by Employee ID, and have information about
Name, Birth date and salary.
f. The customers can be of two types: local customers or non-local customers. Local
customers have information about their local address, and non-local customers have
information about the original city that they come from.
2.1. Given the requirements listed above, draw the equivalent ER diagram (10 pts).
2.2. Given the requirements listed above, draw the equivalent UML diagram (10 pts).
Problem 3. ER Design to Relational Schema (20 pts)
a. Based on the ER diagram above, determine the validity of the following statements. For
each statement, answer true or false and explain your answer in 1-2 sentences. (9 pts)
1. A Restaurant can have many Customers. (3 points)
2. Only one food item can be served by a Restaurant. (3 points)
3. Each Food Item is uniquely identified by its name. (3 points)
b. Use Data Definition Language(DDL) to convert the ER diagram above into a relational
schema. (11 pts)
Problem 4. Multi-Way to Binary Conversion (10 pts)
Convert the following multi-way relationship in the ER Diagram to Binary relationship.
Section 2. Functional Dependencies and
Normal Forms
Problem 5. Attribute Closure and Functional
Dependencies (15 pts)
a. Given a relation R(A,B,C,D,E,F) and functional dependencies FD = {AB->F, D->A,
E->BF, AF->C,BC->D}, answer the following: (10 pts)
1. Calculate the closure of {F}+, {A,B}+,{C,E,F}+, {D}+, {A,C,D,F}+
2. Find all candidate keys of R
b. Given a relation R(A,B,C,D,E) and functional dependencies FD = {B → A; C → A; E →
A; CE → B}, Infer all non-trivial functional dependencies for R. (5 pts)
Problem 6. Normal Forms (45 pts)
a. Consider the following relations R1, R2, R3. Which normal forms (BCNF,3NF) is each
relation in? Explain why the relation is or is not in each of these normal forms. (15 pts)
1. R1 = (A,B,C,D,E) with a set of functional dependencies FD = {C->B,ADE->BC,D->E} (5
pts)
2. R2=(A,B,C,D,E,F) with a set of functional dependencies FD = {C->DF, CF -> B, CD->A,
CBD->E} (5 pts)
3.R3=(A,B,C,D,E,F) with a set of functional dependencies FD = { B->A, BF->DE; AF->C; AC->B}
(5 pts)
b. Given a relation R(A,B,C,D,E) with functional dependencies FD = {E->B, B->A, E->AD, AE->B, BC->D}
(10 pts)
1. Compute the minimal basis of FD. (5pts)
2. Decompose the relation R into a set of relations that are in 3NF.(5pts)
c. Given a relation R(A,B,C,D,E,F) with functional dependencies FD = {F -> DE, B->E, CD -> A, D->C},
and another relation R1(A,B,D,F) is projected from R, compute the set of FDs in R1. (10 pts)
d. Consider the relation R(A,B,C,D,E,F), and the corresponding set of functional dependencies FD =
{A->F,B->E,BF->C,C->DE}. Decompose the relation R into a set of relations that are in BCNF. (10 pts)