CS145 - Introduction to Databases
Spring 2000, Prof. Widom

Written Assignment #3
Due Wednesday April 26

Warning: This is a fairly long assignment, but by the end of it you should have fully mastered relational algebra and SQL. Feel free to leave out portions if you believe you have already mastered the material.

Problem 1

Do parts (a)-(g) of Exercise 4.1.1 in the textbook (pages 187-190).

Problem 2

Consider the following SQL query over relation R(A,B):

SELECT MAX(A) FROM R WHERE B > 5

(a) Can you write this query in relational algebra? If so, show it.

Now consider the following SQL query over the same relation:

SELECT COUNT(*) FROM R WHERE B > 5

(b) Can you write this query in relational algebra? If so, show it.

Problem 3

(a) Do Exercise 4.1.8 in the textbook (page 194), except you only need to give one equivalent expression, not three.

(b) There is another operator called the "antisemijoin," which is similar to the semijoin except it returns the set of all tuples in R that don't agree with any tuple in S on their shared attributes. Write a relational algebra expression equivalent to R antisemijoin S.

Problem 4

Do Exercise 4.6.2 in the textbook (page 237).

Problem 5

Do parts (a), (c), (d), and (e) of Exercise 5.2.2 in the textbook (page 262).

Problem 6

Do parts (b) and (c) of Exercise 5.3.1 in the textbook (page 269). Then for your answers to (b) and (c), continue with Exercise 5.4.3 in the textbook (page 273).

Problem 7

Do parts (e) and (g) of Exercise 5.5.1 in the textbook (pages 277-278).

Problem 8

Do parts (d) and (g) of Exercise 5.6.1 in the textbook (pages 284-285).

Problem 9

Consider a relation Flight(from,to,cost,airline) containing nonstop flights from one city to another. Note that the flights from city A to city B are independent of the flights from B to A. For example:

fromtocostairline
SFDenver300Frontier
SFDenver350United
DenverSF250United
DenverSF250Frontier
DenverChicago250American
ChicagoNY250Delta
DenverNY500American
DenverNY400TWA
SFNY750United

(a) Give a single SQL query that returns the cost of the cheapest nonstop flight between each pair of cities. For example, the result over the above relation instance should be:

fromtocost
SFDenver300
DenverSF250
DenverChicago250
ChicagoNY250
DenverNY400
SFNY750

(b) Give a single SQL query that returns the cheapest cost of flying between each pair of cities assuming we are willing to stop up to two times en-route. For example, by stopping once (in Denver), we can get from SF to NY for 700 instead of 750. With this example data, we could stop twice (in Denver and Chicago), but that would be more expensive ($300+$250+$250 = $800).

(c) Is it possible to write a single SQL query that returns the cheapest cost of flying between each pair of cities regardless of the number of stops? If so, give the query. If not, briefly explain why.

Problem 10

Do Exercise 5.9.5 in the textbook (page 312) except give two equivalent queries with only a single condition in the WHERE clause, not just one equivalent query.

Problem 11: OPTIONAL

Can you write a query in SQL that requires a HAVING clause? That is, can you find a query that uses a HAVING clause, and for which there is no equivalent SQL query that does not use a HAVING clause?