Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 79 ยท Relational Algebra and Calculus

Union, Intersection, Difference and Cartesian Product

Learn the binary operators of relational algebra: union, intersection, set difference and Cartesian product, union compatibility and their SQL equivalents.

Selection and projection work on one relation at a time. Real questions combine several: "who took the first course or the second?", "who took both?", "who took the first but not the second?". Relational algebra answers them with operators borrowed from set theory, because a relation is a set of tuples. This lesson covers the four binary operators: union, intersection, difference and Cartesian product.

The examples use the school dataset. The relation enrollments(student_id, course_id, term_id, grade) records who took which course in which term. Course 6 is CS100 (Programming Basics) and course 7 is CS210 (Databases).

Union compatibility

Set operators only make sense when the two inputs describe the same kind of tuple. Two relations R and S are union compatible when:

  1. they have the same number of attributes, and
  2. the attributes in the same positions have compatible domains (types).

Attribute names are not required to match. By convention the result takes the names from the first relation, and you can use rename to change them. SQL follows the same rule: the SELECT lists on both sides must have the same number of columns.

SQL
-- Shown only: this is rejected because the column counts differ.
SELECT id, name FROM teachers
UNION
SELECT id FROM terms;
-- error: SELECTs to the left and right of UNION do not have the same number of result columns

The four operators

Combining two relations

Union R โˆช S Tuples in R, in S, or in both.
Intersection R โˆฉ S Tuples in both R and S.
Difference R โˆ’ S Tuples in R that are not in S.
Product R ร— S Every tuple of R paired with every tuple of S.

The first three need union-compatible inputs. Product does not.

1 / 2

Union, intersection and difference

Let CS100 be the set of students who took course 6 and CS210 the set who took course 7, projected down to just student_id:

TEXT
A = ฯ€ student_id ( ฯƒ course_id = 6 (enrollments) )
B = ฯ€ student_id ( ฯƒ course_id = 7 (enrollments) )

Then:

  • A โˆช B: students who took at least one of the two courses.
  • A โˆฉ B: students who took both.
  • A โˆ’ B: students who took CS100 but never CS210. Note that difference is not symmetric: B โˆ’ A is a different set.

Intersection is not a new power: A โˆฉ B = A โˆ’ (A โˆ’ B). Algebra keeps it as a convenient shortcut.

SQL Union, intersection and difference of two course rosters ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The counts are 32, 17, 6 and 9. They fit together: 23 students took CS100 and 26 took CS210; the 17 who took both are counted once in the union (23 + 26 โˆ’ 17 = 32).

Sets versus bags

The word "students" matters above. The table enrollments holds 34 rows for course 6 but only 23 different students, because some of them took the course in more than one term. A set cannot contain the same value twice, but a table can. SQL's set operators resolve this for you: UNION, INTERSECT and EXCEPT return sets (duplicates removed), while UNION ALL keeps every row.

SQL UNION removes duplicates, UNION ALL keeps them ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

You get 32 against 74: that is 34 + 40 rows, repeats included. UNION ALL is cheaper because it skips the duplicate-removal step, so use it when duplicates are impossible or harmless.

Union also works across completely different tables, as long as the shapes match. The attribute names come from the first query:

SQL Union across two different tables ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Two things to notice. The two inputs are compatible (one text column each) even though they come from different relations. And the combined list is sorted; ORDER BY applies to the whole result, which is an operation outside the algebra, because relations have no order.

Cartesian product

The Cartesian product R ร— S pairs every tuple of R with every tuple of S. If R has m tuples and S has n, the result has m ร— n tuples, and its schema is the attributes of R followed by those of S. If both have an attribute with the same name, rename one first.

The product has no union-compatibility rule, since it builds a wider tuple instead of merging sets. In SQL it is CROSS JOIN (or the old comma form FROM a, b).

SQL Cartesian product: every term with every 5-credit course ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Here ฯƒ credits=5 (courses) has one row and terms has three, so the product has 3 rows. Now see how fast the product grows.

SQL Product sizes multiply ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

36 students and 10 courses give 360 pairs. Two tables of a million rows each would give a trillion.

Why the product is rarely used alone

A pure product returns mostly nonsense: it pairs a student with courses they never attended. Its real value is as a building block. Selecting only the meaningful pairs gives a join:

TEXT
ฯƒ students.id = enrollments.student_id ( students ร— enrollments )

That composition is so common that algebra gives it its own operator, covered in Joins in Relational Algebra. A DBMS never builds the full product and then filters it. The optimizer recognizes the pattern and uses a join algorithm instead (Join Algorithms). An unintended product is a classic bug: forgetting the join condition in a query makes the row count explode.

Product is also the standard tool for generating combinations, such as every employee-day or every product-size pair, where you want them all.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Two relations are union compatible when they have...

    Names may differ; the result uses the first relation's names. The arity and the domains must line up.
  2. 2. R has 12 tuples and S has 5. How many tuples does R ร— S have?

    The product pairs every tuple of R with every tuple of S, so the size is 12 ร— 5 = 60.
  3. 3. Which statement about set difference is true?

    Order matters: the 6 students who took only CS100 differ from the 9 who took only CS210.
  4. 4. What is the difference between UNION and UNION ALL in SQL?

    UNION follows set semantics and removes duplicates; UNION ALL is the bag version and is cheaper.
  5. 5. Why is a Cartesian product rarely useful on its own?

    Most useful queries follow the product with a selection that keeps the meaningful pairs, which is exactly a join.

Summary

  • Union, intersection and difference need union-compatible inputs: same number of attributes and compatible types.
  • Difference is not symmetric; intersection can be expressed as R โˆ’ (R โˆ’ S).
  • SQL's UNION, INTERSECT and EXCEPT use set semantics; UNION ALL keeps duplicates and is cheaper.
  • The Cartesian product has m ร— n tuples and needs no compatibility; in SQL it is CROSS JOIN.
  • Product followed by a selection is a join, which is why engines never materialize the full product.

Next: the operator built from product plus selection, in Joins in Relational Algebra.