Relational Algebra: Union, Intersection, and Difference

Union-compatible schemas

For union, intersection, and difference to be defined, the two relations must have union-compatible schemas: the same number of columns, with the same column names and the same (or compatible) domain types.

Given $R(A, B, C)$ and $S(A, B, C)$, the set operations are well-formed. If the schemas differ, $\rho$ must be used first to rename columns.

Union ($\cup$)

$R \cup S$ returns all tuples that appear in $R$ or in $S$ (or both). Since RA operates on sets, duplicates are eliminated.

$R \cup S = \{t \mid t \in R \lor t \in S\}$

SQL.

(SELECT * FROM R)
UNION
(SELECT * FROM S);

SQL’s UNION eliminates duplicates by default (set semantics). To keep duplicates, use the non-standard UNION ALL.

Intersection ($\cap$)

$R \cap S$ returns all tuples that appear in both $R$ and $S$.

$R \cap S = \{t \mid t \in R \land t \in S\}$

SQL.

(SELECT * FROM R)
INTERSECT
(SELECT * FROM S);

Intersection can be expressed in terms of difference:

$R \cap S = R - (R - S) = S - (S - R)$

In practice, SQL’s INTERSECT is clearer and the optimiser will handle the equivalent transformation if needed.

Difference ($-$)

$R - S$ returns all tuples that appear in $R$ but not in $S$.

$R - S = \{t \mid t \in R \land t \notin S\}$

SQL.

(SELECT * FROM R)
EXCEPT
(SELECT * FROM S);

Note: SQL uses the keyword EXCEPT rather than MINUS (some other database systems use MINUS).

Difference is not commutative: $R - S \neq S - R$ in general.

Set semantics vs multiset semantics

The RA operators work over sets of tuples. A tuple that appears multiple times in a source table appears at most once in the RA result. This is a key distinction:

Concept	RA	SQL default
Duplicates?	Never (set)	Yes (multiset/bag)
Effect on cardinality	Projection may reduce rows	Projection keeps all rows
UNION	Eliminates duplicates	Eliminates duplicates (but UNION ALL keeps them)

SQL defaults to multiset (bag) semantics. The DISTINCT keyword forces set semantics. This distinction is covered in detail in Lecture 7. For now, assume that SQL queries in these notes use SELECT DISTINCT where needed to match RA set behaviour.

Worked example

Given relations:

$R$:

A	B
1	x
2	y
3	z

$S$:

A	B
2	y
3	z
4	w

Union $R \cup S$:

A	B
1	x
2	y
3	z
4	w

Intersection $R \cap S$:

A	B
2	y
3	z

Difference $R - S$:

A	B
1	x

Difference $S - R$:

A	B
4	w

Summary

• Union, intersection, and difference require union-compatible schemas.
• All three eliminate duplicates in RA (set semantics).
• SQL: UNION, INTERSECT, EXCEPT.
• Difference is non-commutative; intersection can be expressed via difference.