## 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 CS532 Homework 3

(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 CS532 Homework 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 CS532 Homework 3