Relational algebra

The essentials

Relational algebra is a set of operations that take one or two relations as input and produce a new relation as output. SQL queries are built on these operations.

Key points

• Selection (σ): picks the tuples (rows) that satisfy a condition. Degree stays the same; cardinality can fall.
• Projection (π): picks chosen attributes (columns). Cardinality stays the same unless duplicate rows are removed.
• Union (∪): all tuples that are in either relation, with duplicates removed. Both relations must be union compatible: same number of attributes, with matching domains.
• Intersection (∩): tuples common to both relations (also needs union compatibility).
• Set difference (−, MINUS): tuples in the first relation but not in the second. A − B is usually not equal to B − A.
• Cartesian product (×): pairs every tuple of the first relation with every tuple of the second.
• For the Cartesian product of R (degree d₁, cardinality c₁) and S (degree d₂, cardinality c₂): degree = d₁ + d₂ and cardinality = c₁ × c₂.
• A join is a Cartesian product followed by a selection on matching attribute values.

Exam tips

• Selection is horizontal (rows), projection is vertical (columns). In SQL, the WHERE clause does selection and the column list after SELECT does projection.
• For union of A (5 tuples) and B (4 tuples) with 2 tuples in common, the result has 5 + 4 − 2 = 7 tuples.

Common mistakes

• Adding cardinalities in a Cartesian product. They are multiplied; only degrees are added.
• Trying to take the union of relations with different numbers of attributes.