CSCI A114 / INFO I111
Takehome Quiz Four

First semester 2000-2001

Due date
October 6, 6pm.
Late policy
Please turn this either
Work policy
Working in groups is accepted but you need to turn in your own version of the assignment.
Task
Explained in detail below.
Grading
Adrian will provide you with feedback within a week. Grades will be posted on-line.

For the following exercises please recall that a relation is a subset of a cartesian product.

A relation is a set.

1. CARTESIAN PRODUCT

If R and S are two relations of arities k1 and k2 their cartesian product is the set of (k1 + k2) -tuples whose first k1 components form a tuple in R and whose last k2 components form a tuple in S.

For the relations below please compute the cartesian product.

R S
A B
1 1
2 1
0 1
1 3
2 4
C D E
2 1 2
1 3 1

2. PROJECTION

The idea behind projection is that we take a relation R, remove some components (columns, attributes) and/or rearrange some of the remaining components. We denote the operation by P followed by a sequence of indices, that identify the components to be kept, followed by the relation on which the projection is taken.

With S as defined above please compute PC, D(S)

3. SELECTION

If we have a formula F that involves column names, constants, arithmetic comparison operators (<, <=, etc.), and logical operators (such as and, not, or) then we denote selection of tuples according to F as

SF(R)
and it represents the set of all tuples that satisfy condition F.

With R as defined above please compute SA < B (R)

4. JOIN

A join involves two columns: i in R and j in S and a formula F.

If R has arity r then JF(i, j)(R, S) is

SF(i, r+j)(R x S)
where by R x S we denote the cartesian product between R and S.

For the relations R and S defined above please compute JB > C(R, S)

5. NATURAL JOIN

The natural join is applicable when both R and S have columns that are named by attributes. To compute the natural join first compute the cartesian product and then for each attribute A that names both a column in R and a column in S select from the cartesian product those tuples whose values agree in the columns for R.A and S.A.

For the relations below please compute the natural join.

R S
A B D
1 0 1
0 0 2
B C D
0 2 2
1 2 3

Last updated: October 2, 2000 by Adrian German for A114/I111