CSE 594

University of Washington

Autumn 1999

Homework 1

See the web page for some homework guidelines, due dates, and policies.
  1. (30 points) Draw an E/R diagram for a database that will contain information about something you find interesting. You will be working with this database throughout the course: in later homeworks you will create relations based on the E/R diagram, do the physical design, populate it, add some complex constraints, and query it. As a rough guideline, a minimum of about five entity sets (plus the relationship sets needed to relate them) is needed to get a database of sufficient complexity for what we need to do, so choose your application area accordingly. In addition to the E/R diagram, list (in English) any integrity constraints (or other information) that have not been represented in your E/R diagram.


  2. (36 points) For each of the three problems labeled A, B, and C below, do the following:


    1. List all candidate keys for the relation.
    2. State the highest normal form (among those we have discussed) satisfied by the relation.
    3. What redundancies are present in the relation?
    4. Decompose the relation so that the new relations are all in (at least) the next-highest normal form. Write the relation schemas as your answer, indicating primary and foreign keys.
    5. Which, if any, of the redundancies has your decomposition eliminated?
    6. Identify the highest normal form (among those we have discussed) satisfied by each of the new relations.
    7. Is your decomposition lossy or lossless? If it is lossy, give a lossless decomposition.
    8. Does your decomposition preserve dependencies? If not, which are lost? If any are lost, give a new decomposition that preserves all dependencies, or convince me that it is not possible without going back down to a lower normal form.

    Here are the relations and dependencies:
    1. DOG (Name, Breed, MaxSize)

      2. Name ® Breed

      Breed ® MaxSize

    2. CLIENT_INTERVIEW (ClientNum, InterviewDate, InterviewTime, StaffNum, RoomNum)

      3. {ClientNum, InterviewDate} ® {InterviewTime, StaffNum, RoomNum}

      {StaffNum, InterviewDate, InterviewTime} ® ClientNum

      {StaffNum, InterviewDate} ® RoomNum

    3. UNIVERSITY (CourseNum, SecNum, Dept, Credits, Level, Instructor, Semester, Year, Time, Room, NumStudents)

      4. CourseNum ® {Dept, Credits, Level}

      {CourseNum, SecNum, Semester, Year} ® {Time, Room, NumStudents, Instructor}

      {Room, Time, Semester, Year} ® {Instructor, CourseNum, SecNum}
    4. (10 points) Textbook, Exercise 15.16. Describe the algorithm in pseudo-code and explain why it is linear.


    5. (12 points) An Armstrong relation is a relation instance that exemplifies exactly the dependencies that hold over a relation schema R; i.e., all FDs that do not hold over R are violated by the instance. Armstrong Relations are sometimes used in database design to give a DBA example relations based on the functional dependencies provided by the DBA; actual products for DBAs exist that use the concept and some DBAs find it useful to see the consequences of their FDs during the design process. Show an Armstrong Relation for the schema (Instructor, Time, Room) in which the only FD is {Instructor, Time} ® Room. Your answer should use as few tuples as possible.

    6. (12 points) Let F = { AB ® C, A ® B}.
      1. Find a minimal cover for F.
      2. When (a) was given on an exam at a large western university, more than half the class answered G = {A ® B, B ® C}. Show this answer is wrong by giving a relation instance that satisfies F but violates G.