Set Operations in Relational Algebra

Concept

A relation is a set of tuples, so the classical set operations apply directly — with one condition attached.

Union compatibility

Two relations may be combined by union, intersection or difference only if they are union compatible:

1. They have the same degree — the same number of attributes.
2. Corresponding attributes are drawn from the same domains, in the same order.

Attribute names need not match; the result conventionally takes the names of the first operand.

  COMPATIBLE                    NOT COMPATIBLE

  A ( name, city )              A ( name, city )
  B ( name, city )              B ( name, city, pincode )
    same degree, same domains     different degree

  A ( roll_no, name )           A ( roll_no, name )
  B ( staff_no, name )          B ( name, roll_no )
    names differ, domains match   domains in the wrong order
    -> COMPATIBLE                 -> NOT compatible

The sample relations

  CS_STUDENT              EC_STUDENT           SPORTS
  +----+-------+          +----+--------+      +----+-------+
  | 21 | Meera |          | 23 | Anitha |      | 21 | Meera |
  | 22 | Ravi  |          | 24 | Kumar  |      | 23 | Anitha|
  | 25 | Divya |          +----+--------+      | 26 | Farid |
  +----+-------+                               +----+-------+

1. Union

Every tuple appearing in either relation, with duplicates removed.

  NOTATION   R union S

  CS_STUDENT union EC_STUDENT
  +----+--------+
  | 21 | Meera  |
  | 22 | Ravi   |
  | 25 | Divya  |
  | 23 | Anitha |
  | 24 | Kumar  |
  +----+--------+                5 tuples

  CS_STUDENT union SPORTS
  +----+--------+
  | 21 | Meera  |   appears in both, kept ONCE
  | 22 | Ravi   |
  | 25 | Divya  |
  | 23 | Anitha |
  | 26 | Farid  |
  +----+--------+                5 tuples, not 6

  commutative and associative

2. Intersection

Only the tuples appearing in both.

  NOTATION   R intersect S

  CS_STUDENT intersect SPORTS
  +----+-------+
  | 21 | Meera |          Meera is the only student in both
  +----+-------+

  CS_STUDENT intersect EC_STUDENT
  (empty)                 no student is in both departments

  Intersection is NOT a primitive operator. It can always
  be rewritten:

     R intersect S  =  R - ( R - S )

  It is provided for convenience, not necessity.

3. Set difference

Tuples in the first relation that are not in the second.

  NOTATION   R - S

  CS_STUDENT - SPORTS
  +----+-------+
  | 22 | Ravi  |          CS students who do NOT play sport
  | 25 | Divya |
  +----+-------+

  SPORTS - CS_STUDENT
  +----+--------+
  | 23 | Anitha |         sports players who are not CS
  | 26 | Farid  |
  +----+--------+

  NOT commutative. R - S and S - R are different questions
  with different answers, and confusing them is a classic
  exam error.

4. Cartesian product

Every tuple of the first paired with every tuple of the second. Union compatibility is not required, and the operator is usually a step towards a join rather than an end in itself.

  NOTATION   R x S

  degree      = degree(R) + degree(S)
  cardinality = |R| x |S|          <- multiplication

  STUDENT x COURSE   with 5 students and 3 courses
    -> 5 x 3 = 15 tuples, degree 3 + 3 = 6

  +---------+-------+------+--------+-----------+---------+
  | roll_no | name  | dept | code   | title     | credits |
  +---------+-------+------+--------+-----------+---------+
  |   21    | Meera | CS   | CS201  | Databases |    4    |
  |   21    | Meera | CS   | CS202  | Networks  |    3    |
  |   21    | Meera | CS   | EC101  | Circuits  |    4    |
  |   22    | Ravi  | CS   | CS201  | Databases |    4    |
  |   ...                                                 |
  +---------+-------+------+--------+-----------+---------+

  Most of these pairings are meaningless. A product on its
  own is almost never the answer - it is the raw material
  a JOIN filters down.

Product plus selection equals join

  This equivalence is the whole of the next note in one line:

    R  JOIN[condition]  S   =   SELECT[condition]( R x S )

  Conceptually the DBMS forms every pair and keeps the ones
  that match. It never actually does this - forming 5 million
  pairs to keep 2,000 would be absurd - but the DEFINITION is
  the product, and that is what makes joins provable.

Primitive operators

Only six operators are primitive; every other operator can be expressed using them.

Common mistakes

• Applying union to relations of different degree. Check compatibility first, every time.
• Assuming difference is commutative. It is not.
• Forgetting union removes duplicates. It does, because the result is a set.
• Adding the cardinalities of a product. They multiply.
• Thinking intersection is primitive. It is derived from difference.

Exam and interview questions

1. Define union compatibility and give one compatible and one incompatible pair.
2. Which set operations are commutative and which are not?
3. Express intersection using only primitive operators.
4. State the degree and cardinality of a Cartesian product.
5. List the six primitive relational algebra operators.

Practice

1. Using the sample relations, compute SPORTS - CS_STUDENT and state what the result means in words.
2. A relation has 4 tuples and degree 3; another has 6 tuples and degree 2. Give the degree and cardinality of their product.
3. Write an expression for students who are in CS but do not play sport, using difference.
4. Explain why STUDENT union COURSE is invalid.

Conclusion

Union, intersection and difference need union compatibility; product needs none and multiplies cardinality. The equivalence worth memorising is that a join is a selection applied to a product — it is the definition every join operator in the next note is built on.