Selection / Cartesian Product

Selection / Cartesian Product


The selection operator, applied to a relation R, creates a new relation with a subset of R's tuples. The tuples in the resulting relation are those that satisfy some condition C that involves the attributes of R. We denote this operation σC(R). The schema for the resulting relation is the same as R's schema, and we normally show the attributes in the same order as we use for R.

C is a conditional expression of the type with which we are familiar from conventional programming languages; for instance, conditional expressions follow the keyword if in programming languages such as C or Java. The only difference is that the operands in condition C are either constants or attributes of R. We apply C to each tuple t of R by substituting, for each attribute A appearing in condition C, the component of t for attribute A. If after substituting for each attribute of C the condition C is true, then t is one of the tuples that appear in the result of σC(R); otherwise t is not in the result.

Example (a) : Let the relation Movie be as in "Set Operations on Relations"  Figure (b). Then the value of expression σlength≥100(Movie)  is

The first tuple satisfies the condition length ≥ 100 because when we substitute for length the value 124 found in the component of the first tuple for attribute length, the condition becomes 124 ≥ 100. The latter condition is true, so we accept the first tuple. The same argument explains why the second tuple of "Set Operations on Relations" Figure (b) is in the result.

The third tuple has a length component 95. Thus, when we substitute for length we get the condition 95 ≥ 100, which is false.  Hence the last tuple of  "Set Operations on Relations"  Figure (b) is not in the result.

Example (b) : Assume we want the set of tuples in the relation Movie that represent Fox movies at least 100 minutes long. We can get these tuples with a more complex condition, involving the AND of two subconditions. The expression is

The tuple

is the only one in the resulting relation.

Cartesian Product

The Cartesian product (or cross-product, or just product) of two sets R and S is the set of pairs that can be formed by choosing the first element of the pair to be any element of R and the second any element of S. This product is denoted R x S. When R and S are relations, the product is basically the same. On the other hand, since the members of R and S are tuples, generally consisting of more than one component, the result of pairing a tuple from R with a tuple from S is a longer tuple, with one component for each of the components of the constituent tuples. By convention, the components from R precede the components from S in the attribute order for the result.

The relation schema for the resulting relation is the union of the schemas for R and S. On the other hand, if R and S should happen to have some attributes in common, then we need to invent new names for at least one of each pair of the same attributes. To disambiguate an attribute A that is in the schemas of both R and S, we use R.A for the attribute from R and S.A for the attribute from S.

Two relations and their Cartesian products

Example (c) :
For conciseness, let us use an abstract example that shows the product operation. Let relations R and S have the schemas and tuples shown in Figure (a). Then the product R x S consists of the six tuples shown in that figure. Note how we have paired each of the two tuples of R with each of the three tuples of S. Since B is an attribute of both schemas, we have used R.B and S.B in the schema for R x S. The other attributes are unambiguous and their names appear in the resulting schema unchanged.