The Databases Course

Exercise No. 2

Relational Algebra

Due on December 29th by midnight

 

Note: This is the HTML format of the exercise, so some special symbols cannot be viewed or printed well. There's also a Word '95 version and Word '97 version, which do not have this problem.

 

  1. (Thanks to Yael Arad) The following relations are given:

Chessman(cid, type, color)
Chessboard(x, y, cid)

The Chessman relation includes data on all the pieces participating in the game: Each piece has a unique identifier cid, a type (king, queen, rock, bishop, knight or pawn) and a color (black or white). The Chessboard relation describes the game board at the given instance during a game: A tuple (x,y,cid) means that the piece cid is at coordinates (x,y) on the board. Express the following queries in relational algebra:

The queries should be clearly explained! Also, your queries should be as efficient as possible: For example, try to use selection and projection as early as possible, and avoid redundant cartesian products.

 

  1. Given is a relation R(id, age) that describes a team's members (by unique id's) and their ages. Consider the following query:

Õ id ( R – Õ R1.id, R1.age (s R1.age < R2.age ( R1 ´ R2 ) ) )

 

  1. For the following pairs of queries, prove whether they are equal, one of them is contained in the other, or neither of these is always true. R1 and R2 are two different relations with the same schema SR, and T is a relation whose schema is ST Í SR.

 

  1. Assume that R and S have one similar field, and their natural join needs to be computed. Explain how this can be done in O((m+n) * log(m+n)) time, where m and n are the number of tuples in R and S, respectively.

 

Look at last year's exercise 2 as well. Study Question 2 and its answer in particular.