COS 425, Fall 2006 - Problem Set 2
Due at 1:30pm Wednesday, October 11, 2006
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.
Late Penalties
- 10% of the earned score if submitted after class but by 5pm the
day due.
- 30% of the earned score if submitted by 5pm on Friday 10/13/06.
- No credit if submitted later than the 30% penalty
deadline
Note: Given a relation R:(a,b,c,d), the text refers to
each
of a, b, c and d as a "field" and I have been
using "attribute" or sometimes
"component."
1. (10 points)
In class we used the following example:
Relation tp: (name, rank) represents a
tennis player by name and rank (think of ranks as groupings, e.g.
"top 5").
tp ◊◊
ρ( tp2(1 →
name2), tp) where ◊◊ denotes natural join, gives triples (name, rank, name2) such that name and name2 both have rank.
However, because name is distinct from name2 but they range over the same
values, there will be two triples for each actual pair of
names: (Sharapova, top 5, Hingis) and (Hingis, top 5,
Sharapova). There will also be self-pairings: (Hingis, top
5, Hingis). How might you eliminate such duplicates using
a relational algebra expression?
2. (10 points)
Give an example of two relations R
and Q and a tuple of R that is not in (R /
Q ) X Q . You must specify all the
tuples in R and Q. It is fine for R and Q to be small, but R/Q
must not be empty.
3. (20 points)
Part a: Let R be a relation with attributes (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 attribute x, the primary key of
relation X. Let
Q be a relation with attributes (e,f,g,h) over domains A, B, C, and D,
respectively. Let {g,h} be a candidate key for Q, and let {e,h} be a
foreign
key referencing attributes {y,z}, the primary key of relation Y. What
candidate key and
foreign key constraints must
be true of R-Q?
Part b: Let R again be a relation with attributes (a,b,c,d)
over
domains A,B,C, and D, respectively. Again let {a} and {b,c} be two
candidate
keys for R and let {b} be a foreign key referencing attribute x, the
primary key of relation
X. Let T be a relation with attributes (c,d) over domains C and D,
respectively.
Let {c} be a candidate key for T and let {d} be a foreign key
refererencing attribute u, the primary key of relation U. What
candidate key and foreign key constraints
must be true of R/T?
4. (30 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)
- name is a foreign key referencing employee
- relation manages with attributes (employee_name,
manager_name)
- employee_name is a foreign key referencing works
- manager_name is a foreign key referencing works
Express the following queries with relational algebra expressions. You
may use any relational algebra operations, including joins and
division.
- Find the names of all employees who work for Microsoft and draw a
salary
of no more than $30,000.
- Find the names and employer's name of all employees who live in
Trenton
and draw a salary of more than $1,000,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 and addresses of all employees who earn more than
every
manager of IBM.
- 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. (30 points) Express the queries of Problem 4 in the tuple
relational
calculus.