Natural Join

Definition

The natural join (denoted $\bowtie$) is the RA operator that combines two relations by equating columns with the same name and eliminating duplicate columns from the output.

Schema notation

When we write the schema of $R$ as $R(A, B)$, we mean that the schema is $R(A \cup B)$ where $A$ and $B$ are disjoint sets of attributes. The notation splits the schema into parts for clarity: $A$ are the attributes unique to $R$, $B$ are the shared attributes.

Formal definition

Given $R(A, B)$ and $S(B, C)$, where $B$ is the set of attributes shared by both relations, the natural join $R \bowtie S$ is a relation over attributes $A \cup B \cup C$ defined as:

$R \bowtie S = \{t \mid \exists u \in R,\; v \in S,\; u.[B] = v.[B] \land t = u.[A] \cup u.[B] \cup v.[C]\}$

That is: for every pair of tuples $(u, v)$ from $R$ and $S$ where the shared attributes match ($u.[B] = v.[B]$), the result tuple $t$ combines $u$‘s unique attributes ($u.[A]$), the shared attributes ($u.[B]$, which equals $v.[B]$), and $v$‘s unique attributes ($v.[C]$).

The shared attributes $B$ appear once in the result, not twice.

RA expression for natural join

The natural join can be expressed in terms of primitive RA operators:

$R \bowtie S = \pi_{A, B, C}\left(\sigma_{B = B'}\left(R \times \rho_{\vec{B} \mapsto \vec{B'}}(S)\right)\right)$

The steps:

1. Rename the shared columns in $S$ to distinguish them from those in $R$: $\rho_{\vec{B} \mapsto \vec{B'}}(S)$.
2. Take the Cartesian product: $R \times \rho_{\vec{B} \mapsto \vec{B'}}(S)$.
3. Select rows where the shared columns are equal: $\sigma_{B = B'}(\cdots)$.
4. Project to remove the duplicate columns: $\pi_{A, B, C}(\cdots)$.

The notation $B = B'$ abbreviates the conjunction of equalities on each attribute in $B$: $u.B_1 = v.B'_1 \land \cdots \land u.B_n = v.B'_n$.

SQL translation

SQL provides NATURAL JOIN:

SELECT *
FROM R
NATURAL JOIN S;

This automatically equates all columns with the same name. More commonly, explicit joins are used:

SELECT *
FROM R
INNER JOIN S ON R.B = S.B;

Worked example

Students(name, sid, cid) — student name, ID, and the college ID they belong to.

name	sid	cid
Alice	a1	C1
Bob	b1	C2
Carol	c1	C1

Colleges(cid, cname) — college ID and college name.

cid	cname
C1	Churchill
C2	King’s
C3	Trinity

Students $\bowtie$ Colleges:

name	sid	cid	cname
Alice	a1	C1	Churchill
Bob	b1	C2	King’s
Carol	c1	C1	Churchill

The join matches on the shared cid column. Alice and Carol are both matched to Churchill. Bob is matched to King’s. College C3 (Trinity) has no students, so it does not appear in the result. If a student had a cid with no matching college, that student would also be excluded.

Join variations in SQL

Beyond the natural join, SQL supports several join types. These go beyond core RA but are essential in practice:

Join type	SQL syntax	Behaviour
Inner join	INNER JOIN / JOIN	Rows with matching values in both tables
Left outer join	LEFT JOIN	All rows from left table; NULLs for unmatched right rows
Right outer join	RIGHT JOIN	All rows from right table; NULLs for unmatched left rows
Full outer join	FULL JOIN	All rows from both; NULLs where no match
Cross join	CROSS JOIN	Cartesian product (no join condition)

When NULL values are present in the data, the behaviour of joins becomes more nuanced — see the textbook (Lemahieu 7.3.1.5) for details.

Join conditions beyond equality

The natural join only handles equality on shared columns. SQL generalises this with arbitrary join predicates:

SELECT *
FROM Employees e
JOIN Departments d ON e.dept_id = d.dept_id AND e.salary > d.budget;

In RA, a non-equality join must be expressed via product and selection:

$\sigma_{\text{dept\_id} = \text{dept\_id}' \;\land\; \text{salary} > \text{budget}}(R \times \rho_{\{\ldots\}}(S))$

Summary

• $R \bowtie S$ equates shared columns and eliminates duplicates.
• RA definition: $\pi_{A,B,C}(\sigma_{B=B'}(R \times \rho_{\vec{B} \mapsto \vec{B'}}(S)))$.
• SQL: NATURAL JOIN or INNER JOIN ... ON.
• Outer joins (LEFT, RIGHT, FULL) preserve unmatched rows with NULLs.
• Non-equality join predicates require product + selection in RA.