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:

• Which type of pieces does black currently have on the board?
• Find all the pieces that are in the moving axis of the rock whose cid is c5. A rock may move along the row or column it is at, in any direction.
• Normally, each player may have at most two knights. Under this assumption, find the color that currently has more knights on the board.
• Find types of which there are at least two pieces, of any color, on the board.
• Which players (colors) still have all their pawns on the board?
• Which players have at least all the types of pieces the opposite player has?
• Given are two relations board1 and board2 whose schema is identical to that of chessboard, that represent two consecutive states of a game, before and after a move. Which piece was moved?
• Continuing the last question, where was the piece moved from?
• Moving to a square that contains a piece of the opposite color involves taking that piece off the board. Was a piece removed in the last move, and if so, which one was it?

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.

2. 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} ( R₁ ´ R₂ ) ) )

• What does the query compute?
• What is computed if the '<' is replaced by '>'?
• What goes wrong if the '<' is replaced by '<='?

3. 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. R₁ and R₂ are two different relations with the same schema S_R, and T is a relation whose schema is S_T Í S_R.

• P _A(R₁ – R₂) versus P _A(R₁) – P _A(R₂)
• P _A(R₁ È R₂) versus P _A(R₁) È P _A(R₂)
• P _A(R₁ Ç R₂) versus P _A(R₁) Ç P _A(R₂)
• s _F1 (R₁) > < s _F2 (R₂) versus s _{F1 Ú F2} (R₁ > < R₂)
• s _F1 (R₁) > < s _F2 (R₂) versus s _{F1 Ù F2} (R₁ > < R₂)
• ( R ¸ T) ´ T versus R

4. 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.