Description
1. The following are some of the relations transformed from the ER diagram for the Student
Registration System (note that some changes have been made due to the creation of a singleattribute key for Classes):
Students(sid, firstname, lastname, status, gpa, email)
Courses(dept_code, course#, title, credits, deptname)
Classes(classid, dept_code, course#, sect#, year, semester, start_time, end_time,
limit, size, classroom, capacity, fid) /* note: classid is added to serve as a single-attribute key */
Faculty(fid, firstname, lastname, rank, office, email, deptname)
Enrollments(sid, classid, lgrade, ngrade)
Do the following for each relation schema:
(a) (20 points) Identify all non-trivial functional dependencies. Don’t make unrealistic
assumptions about the data. Use the union rule to combine the functional dependencies as
much as possible. Furthermore, if a functional dependency is redundant (i.e., it can be
derived from the ones you keep), don’t include it.
(b) (20 points) Determine whether or not the schema is in 3NF or in BCNF. Justify your
conclusion.
(c) (20 points) For each schema that is not in 3NF, decompose it into 3NF schemas using
Algorithm LLJD-DPD-3NF. Show the result after each step of the algorithm. Are the
decomposed schemas in BCNF? Justify your answer.
2. (14 points) Prove or disprove the following rules:
(a) {B CD, AB E, E C} |= {AE CD}
(b) {B CD, AD E} |= {AB E}
When proving a rule, you can use all the six inference rules (i.e., reflexivity rule,
augmentation rule, transitivity rule, decomposition rule, union rule and pseudotransitivity
rule). To disprove a rule, construct a relation with appropriate attributes and tuples such that
the tuples of the relation satisfy the functional dependencies on the left of the rule but do not
satisfy the functional dependency on the right of the rule.
3. (26 points) Write relational algebra expressions to answer the following query
statements based on the tables given in page 3 of this document. For each query, show
the result that would be obtained if the query were actually executed against the tables. It is
OK to answer a query in multiple steps. You need to make sure that your relational algebra
expressions are reasonably optimized as we discussed in class, i.e., conditions involving a
single table should be specified on that table directly and Cartesian products should be
replaced by joins whenever possible.
2
(a) (6 points) Find the dept_code, course# and title of each course that was offered in the
Spring semester of 2014.
(b) (6 points) Find the first name of each student who has taken at least one CS course and at
least one Math course.
(c) (7 points) Find the dept_code and course# of each course that was not offered in 2013.
(d) (7 points) Find the sid and first name of every student who has taken all CS classes
offered in Spring 2014.
3
Tables for Homework 3 Question 3
Students
Sid Firstname Lastname Status GPA email
B001 Anne Broder junior 3.17 broder@bu.edu
B002 Terry Buttler senior 3.0 buttler@bu.edu
B003 Tracy Wang senior 4.0 wang@bu.edu
B004 Barbara Callan junior 2.5 callan@bu.edu
B005 Jack Smith graduate 3.0 smith@bu.edu
B006 Terry Zillman graduate 4.0 zillman@bu.edu
B007 Becky Lee senior 4.0 lee@bu.edu
B008 Tom Baker freshman baker@bu.edu
Courses
Dept_code Course# Title
CS 432 database systems
Math 314 discrete math
CS 240 data structure
Math 221 calculus I
CS 532 database systems
CS 552 operating systems
BIOL 425 molecular biology
Classes
Classid Dept_code Course# Sect# Year Semester Limit Size
c0001 CS 432 1 2014 Spring 35 34
c0002 Math 314 1 2013 Fall 25 24
c0003 Math 314 2 2013 Fall 25 22
c0004 CS 432 1 2013 Spring 30 30
c0005 CS 240 1 2014 Spring 40 39
c0006 CS 532 1 2014 Spring 29 28
c0007 Math 221 1 2014 Spring 30 30
Enrollments
Sid Classid Grade
B001 c0001 A
B002 c0002 B
B003 c0004 A
B004 c0004 C
B004 c0005 B
B005 c0006 B
B006 c0006 A
B001 c0002 C
B003 c0005
B007 c0007 A
B001 c0003 B
B001 c0006 B
B001 c0004 A
B001 c0005 B
4