CSE 444 Midterm Exam (Autumn 1998) SOLUTIONS

1. Consider a database schema with the following relations:
2. Student (ssn, name)

Prof (ssn, name)

Course (number, instructor-ssn, title, credits, room#)

Enroll (student-ssn, course#)

Room (number, capacity)

1. Write a relational algebra query that finds the names of all students who are enrolled in a class taught by "Jones," AND are enrolled in a class called "Physics."
2.

JonesCourse#s = Project<number> [Select<name="Jones"> (Prof Join<ssn=instructor-ssn> Course)]

JonesStudents = Project<ssn> [Student Join<ssn=student-ssn> (Enroll Join<course#=number> JonesCourse#s)]

PhysicsStudents = Project<ssn> [Student Join<ssn=student-ssn> Select<title="Physics"> (Enroll Join<course#=number> Course)]

Answer = Project<name> [Student Join<ssn=ssn>(JonesStudents Intersect PhysicsStudents)]

3. Write a relational algebra query that finds the names of all students who are NOT enrolled in two classes held in the same room.

StudentCourseRoom = Project<ssn,room#,course#> (Enroll Join<course#=number> Course)

SameRoomStudents = Project<ssn> (StudentCourseRoom Join<ssn=ssn & room#=room# & course# != course#> StudentCourseRoom)

AllStudents = Project<ssn> Student

Answer = Project<name> [Student Join<ssn=ssn>(AllStudents – SameRoomStudents)]

3. Using the schema from question (1),
1. Write an SQL query that lists, in alphabetical order, the title of all courses either taught by "Smith" OR are taught in room number 444. Do not list duplicate titles.
2.

SELECT distinct title

FROM course

WHERE number in

(SELECT number FROM course, prof

WHERE instructor-ssn = ssn AND name = "Smith")

OR room# = 444

ORDERBY title

3. Write an SQL query that considers all the courses that have ever been taught by "Brown" and are of 3 credits, and groups them according to title. For each course, the query gives the average capacity of rooms in which the course has been offered, and the query only returns courses for which this average is more than 20.

SELECT title, AVG(capacity)

FROM course, room

WHERE room# = room.number

AND credits = 3

AND course.number in

(SELECT number FROM course, prof

WHERE instructor-ssn = ssn and name = "Brown")

GROUP BY title

HAVING AVG(capacity) > 20

4. Render the database from question (1) in the E/R model. Make sure to indicate that every course has a unique instructor and room.
5. For the following schema and set of FDs,
1. What are the keys of the relation?
2. What are the BCNF violations, if any? (List only FDs with one attribute on the right side.)
3. Decompose the relation, as necessary, into collections of BCNF relations.

R(A,B,C,D) with FDs BC -> D, C -> A, AB -> C

Keys: AB, BC

Violations: C -> A, CD -> A

Decomposition: (B,C,D) and (C,A)