The Databases Course

Exercise No. 4

Relational Algebra, Calculus and QBE

Due on December 16th by midnight

This is a very important exercise - it summarizes the subject of query languages. However, it is slightly bigger than the other exercises. To encourage you to do it anyway, anyone who submits this exercise will get an automatic bonus of two points. So the maximum grade is 22 out of 20!

1. You should by now be very familiar with the database of Suppliers, Parts, Projects and Shipments from exercises 2 and 3 - you already wrote the six queries described in exercise 2 in relational algebra, SQL and tuple relational calculus.
   Write these same six queries (from exercise 2 question 1) in the domain relational calculus.

2. Express the following query in QBE (Query by Example):
   What are the names of suppliers in Paris which supply red parts?

3. The beer drinkers' database contains the following relations:
   Frequents(drinker, bar) , Serves(bar, beer) , Likes(drinker, beer)
   The first indicates the bars each drinker visits, the second tells what beers each bar serves, and the last indicates which beers each drinker lines to drink. Note: A drinker may not like any beer, a bar may not serve any beers, etc.
   Express the following queries in both relational algebra and the safe tuple relational calculus:

1. Find the drinkers that frequent only bars that serve some beer that they like.
2. Find the drinkers that frequent no bar that serves a beer that they like.

4. A query is called monotone if enlarging any of its input relations will not decrease its output relation. Are the queries in question 3 monotone? Prove your answer.

5. Give a complete proof that none of the union, cartesian product, projection and substraction operators can be expressed in terms of the remaining relational algebra operators, i.e. that projection cannot be expressed in terms of union, product, selection and substraction, etc.
   Hint: For each operator, look for the type of queries that need this operator the most. For example, projection is the only operator that lets you return a relation with less attributes than the input relation, substraction is the only non-monotone operator, and so on.

6. We examine a query Q(R1, ..., Rn) over a given database. For all i=1..n Ri has ti tupples and si attributes. The result of the query is a relation with tq tupples and sq attributes. Q may be any well defined query in relational algebra, and we assume that all atomic values appearing in the output must also appear in the input (no calculated fields, etc.). We also assume that Q contains exactly q operators.

1. Show an upper bound for the number of tuples that can belong to the answer of Q.
2. Show that this bound can be achieved using the relational algebra (or calculus).
3. Is there such a bound in the SQL Model, where a table may contain duplicate rows?