Relational Algebra: Product and Renaming

Product ($\times$)

The RA product is based on the Cartesian product but adapted for database relations. Given $R(A_1, \ldots, A_m)$ and $S(B_1, \ldots, B_n)$, the product $R \times S$ returns a relation over the combined attributes $A_1, \ldots, A_m, B_1, \ldots, B_n$.

Mathematically, the Cartesian product of two relations (as sets of tuples) would return pairs of tuples:

$\{(t, u) \mid t \in R, u \in S\}$

The RA product instead returns tuples formed by concatenating the fields of each pair:

$\{t \cdot u \mid t \in R, u \in S\}$

where $\cdot$ denotes tuple concatenation.

Example. Suppose:

$R$:

A	B
1	x
2	y

$S$:

C	D
p	10
q	20

$R \times S$:

A	B	C	D
1	x	p	10
1	x	q	20
2	y	p	10
2	y	q	20

If $R$ has $m$ rows and $S$ has $n$ rows, the product has $m \times n$ rows.

Column name disjointness

A critical constraint: the schemas of $R$ and $S$ must have disjoint column names. If both relations have a column called id, the product would have two columns both called id, which is not a valid relation.

When column names overlap, renaming is required first. For example, if $R(A, B)$ and $S(B, C)$ share column $B$:

$\rho_{\{B \mapsto B'\}}(S)$

produces $S'(B', C)$, and then:

$R \times S'$

produces a valid relation over $(A, B, B', C)$.

SQL translations

There are two equivalent SQL formulations of the product:

Explicit syntax (preferred).

SELECT A, B, C, D
FROM R CROSS JOIN S;

Implicit syntax (comma-separated tables).

SELECT A, B, C, D
FROM R, S;

Both produce the same result. The CROSS JOIN form makes the intent more explicit.

The product is rarely used alone

The product itself is of limited practical use. Its value comes from combining it with selection to form a join. Selecting the product rows where matching columns are equal gives the natural join or equi-join:

$\sigma_{B = B'}(R \times \rho_{\{B \mapsto B'\}}(S))$

This pattern is so common that SQL provides a dedicated JOIN ... ON syntax, and RA has the derived $\bowtie$ (natural join) operator (see following note).

Combining product with renaming

When writing RA expressions involving product, the standard pattern is:

1. Rename overlapping columns in one or both sub-queries with $\rho$.
2. Apply $\times$ to the renamed sub-queries.
3. Apply $\sigma$ to select matching rows.
4. Apply $\pi$ to remove duplicate columns.

Example. Find all pairs of students and lecturers in the same college:

$\pi_{\text{name}, \text{lname}}(\sigma_{\text{Students.college} = \text{Lecturers.college}}(\text{Students} \times \rho_{\{\text{name} \mapsto \text{lname},\; \text{college} \mapsto \text{lcollege}\}}(\text{Lecturers})))$

But this is verbose. The natural join $\bowtie$ (next note) simplifies it.

Summary

• $R \times S$ concatenates tuples; the result has $|R| \times |S|$ rows.
• Column names of $R$ and $S$ must be disjoint; use $\rho$ when they overlap.
• SQL: CROSS JOIN or comma-separated tables in FROM.
• The product is typically combined with selection to form a join.