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."

      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.

      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)