CSE 444

University of Washington

Winter 2000

Homework 2

See the web page for some homework guidelines and policies.

DUE: at beginning of class, Wednesday January 26

  1. (45 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. Give a lossless decomposition of the relation such 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. 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

    3. EMP_PROJECTS (Ssn, Pnumber, Ename, Pname, Hours, Plocation)
    4. {Ssn, Pnumber} ® Hours

      Ssn ® Ename

      Pnumber ® {Pname, Plocation}

    5. GAMES (VisitingTeam, GameDate, GameTime, Referee, Rink)
    6. {VisitingTeam, GameDate} ® {GameTime, Referee, Rink}

      {Referee, GameDate, GameTime} ® VisitingTeam

      {Referee, GameDate} ® Rink

    7. (5 points) Exercise 15.10; ignore the MVDs (dependencies 2, 4, and 6).


    8. (10 points) Exercise 15.22 ("key" means "candidate key" in this question).

    9. (40 points)

      You will write relational algebra queries against a DB whose schema is described as follows in SQL. Assume all relations are in BCNF.

      /* EMPLOYEE; foreign key referencing department is added later */

      create table employee (fname char(10), minit char, lname char(10), ssn numeric primary key, bdate smalldatetime, address char(30), sex char, salary numeric, superssn numeric references employee (ssn), dno numeric)

      /* DEPARTMENT */

      create table department (dname char(20), dnumber numeric primary key, mgrssn numeric references employee (ssn), mgrstartdate smalldatetime)

      /* Foreign key from EMPLOYEE to DEPARTMENT */

      alter table employee add foreign key (dno) references department (dnumber)

      /* DEPT_LOCATIONS */

      create table dept_locations (dnumber numeric references department (dnumber), dlocation char(15))

      alter table dept_locations add primary key (dnumber, dlocation)

      /* PROJECT */

      create table project (pname char(20), pnumber numeric primary key, plocation char(15), dnum numeric)

      alter table project add foreign key (dnum, plocation) references dept_locations (dnumber, dlocation)

      /* WORKS_ON */

      create table works_on (essn numeric references employee (ssn), pno numeric references project (pnumber), hours numeric(18,1))

      alter table works_on add primary key (essn, pno)

      /* DEPENDENT */

      create table dependent (essn numeric references employee (ssn), dependent_name char(10), sex char, bdate smalldatetime, relationship char(10))

      alter table dependent add primary key (essn, dependent_name)

      Write the following queries in relational algebra. If a query can not be expressed in the relational algebra, explain why.

      1. Retrieve the social security numbers of all employees who work more than 30 hours per week on some project.
      2. Retrieve the last names of all employees who work more than 30 hours per week on some project.
      3. Retrieve the social security numbers of all employees having the largest number of dependents.
      4. Retrieve the last name and social security number of all employees born after their manager’s start date. Do not use the relational algebra selection operator (you may use join).
      5. Retrieve the social security numbers of all employees making the lowest salary.
      6. Retrieve the last names of all employees who work more than 30 hours per week on some project but do not work less than 10 hours per week on any project.
      7. Retrieve the sex of all dependents. How many tuples will be in the result of this query?
      8. Retrieve the last names of employees who either have a salary greater than 100000 or work in the "Yacht" department.