COS 425, Spring 2000 - Problem Set 2

Collaboration Policy

You may discuss problems with other students in the class. However, each student must write up his or her own solution to each problem independently. That is, while you may formulate the solutions to problems in collaboration with classmates, you must be able to articulate the solutions on your own.

1. (10 points) In Database Management Systems by Ramakrishnan and Gehrke, Chapter 4, exercise 4.4 pg. 117, parts 1 and 2.

2. (15 points) Can the order of selection and projection operating on a relation R always be reversed? That is, given a relation R, is it always true that the relation resulting from selection by a predicate P on a set of named fields F of R applied to (the projection of R on a subset of named fields G of R) is equal to the relation resulting from projection on a subset of named fields G of R applied to (the selection from R by a predicate P on named fields F of R) ?
If your answer is "yes", give a rigorous argument as to why. If your answer is "no", give an example where changing the order of selection and projection changes the result and give any conditions under which reordering of selection and projection will be guaranteed to give the same result.

3. (10 points) Let R be a relation with fields (a,b,c,d) over domains A,B,C, and D, respectively. Let {a} and {b,c} be two candidate keys for R. Let {b} be a foreign key referencing field x of relation X. Let S be a relation with fields (c,d) over domains C and D, respectively. Let {c} be a candidate key for S and let {d} be a foreign key referencing field y of relation Y. What candidate key and foreign key constraints must be true of R/S?

4. (25 points) For this problem we will use the following relational database (this database and some of the questions come from the recommended text Database System Concepts by Silberschatz, Korth and Sudarshan. )

• relation employee with attributes (name, street, city)
• relation company with attributes (co_name, city)
• relation works with attributes (name, co_name, salary)
• relation manages with attributes (employee_name, manager_name)

Express the following queries with relational algebra expressions. You may use any relational algebra operations, including joins and division.

• Find the names and cities of residence of all employees who work for Summit Bank.
• Find the names of all employees who work for Summit Bank and earn more than $100,000 per year.
• Find all triples representing an employee's name, the employee's salary, and the salary of the employee's manager.
• Find the names of all companies that do not have a location in Princeton.
• Find the names of all employees who earn more than every employee of Fred's Pizza Co.
• Assume companies may be located in several cities. Find the names of all companies located in every city in which Fred's Pizza Co. is located.

5. (25 points)Express the queries of Problem 4 in the tuple relational calculus.

6. (15 points)Express the queries of Problem 4 in the domain relational calculus.