Editing Relational algebra (section)

=== Natural join ===
{{redirect|Natural join|the SQL implementation|Natural join (SQL)}}
{{redirect|⋈|the band sometimes represented by this symbol|The Armed}}
Natural join (⨝) is a [[Binary relation|binary operator]] that is written as (''R'' ⨝ ''S'') where ''R'' and ''S'' are [[relation (database)|relation]]s.{{efn|In [[Unicode]], the join symbol is ⨝ (U+2A1D), and the bowtie symbol, occasionally used instead, is ⋈ (U+22C8).}} The result of the natural join is the set of all combinations of tuples in ''R'' and ''S'' that are equal on their common attribute names. For an example consider the tables ''Employee'' and ''Dept'' and their natural join:{{citation needed|date=April 2022}}

{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''Employee''
 |-
 ! Name   !! EmpId !! DeptName
 |-
 | Harry  || 3415  || Finance
 |-
 | Sally  || 2241  || Sales
 |-
 | George || 3401  || Finance
 |-
 | Harriet || 2202 || Sales
 |-
 | Mary   || 1257 || Human Resources
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Dept''
 |-
 ! DeptName   !! Manager
 |-
 | Finance  || George
 |-
 | Sales  || Harriet
 |-
 | Production || Charles
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+  ''Employee''&nbsp;⨝&nbsp;''Dept''
 |-
 ! Name   !! EmpId !!  DeptName   !! Manager
 |-
 | Harry  || 3415   || Finance  || George
 |-
 | Sally  || 2241   || Sales  || Harriet
 |-
 | George || 3401  || Finance || George
 |-
 | Harriet || 2202 || Sales || Harriet
|}
{{col-end}}

Note that neither the employee named Mary nor the Production department appear in the result. Mary does not appear in the result because Mary's Department, "Human Resources", is not listed in the Dept relation and the Production department does not appear in the result because there are no tuples in the Employee relation that have "Production" as their DeptName attribute.

This can also be used to define [[composition of relations]].  For example, the composition of ''Employee'' and ''Dept'' is their join as shown above, projected on all but the common attribute ''DeptName''.  In [[category theory]], the join is precisely the [[fiber product]].

The natural join is arguably one of the most important operators since it is the relational counterpart of the logical AND operator. Note that if the same variable appears in each of two predicates that are connected by AND, then that variable stands for the same thing and both appearances must always be substituted by the same value (this is a consequence of the [[idempotence]] of the logical AND). In particular, natural join allows the combination of relations that are associated by a [[foreign key]]. For example, in the above example a foreign key probably holds from ''Employee''.''DeptName'' to ''Dept''.''DeptName'' and then the natural join of ''Employee'' and ''Dept'' combines all employees with their departments. This works because the foreign key holds between attributes with the same name. If this is not the case such as in the foreign key from ''Dept''.''Manager'' to ''Employee''.''Name'' then these columns must be renamed before taking the natural join. Such a join is sometimes also referred to as an '''equijoin'''.

More formally the semantics of the natural join are defined as follows:

{{NumBlk|:|<math>R \bowtie S = \left\{ r \cup s \ \vert \ r \in R \ \land \ s \in S \ \land \ \mathit{Fun}(r \cup s) \right\}</math>|{{EquationRef|1}}}}

where ''Fun(t)'' is a [[Predicate (mathematics)|predicate]] that is true for a [[Relation (mathematics)|relation]] ''t'' (in the mathematical sense) [[iff]] ''t'' is a function (that is, ''t'' does not map any attribute to multiple values). It is usually required that ''R'' and ''S'' must have at least one common attribute, but if this constraint is omitted, and ''R'' and ''S'' have no common attributes, then the natural join becomes exactly the Cartesian product.

The natural join can be simulated with Codd's primitives as follows. Assume that ''c''<sub>1</sub>,...,''c''<sub>''m''</sub> are the attribute names common to ''R'' and ''S'', ''r''<sub>1</sub>,...,''r''<sub>''n''</sub> are the
attribute names unique to ''R'' and ''s''<sub>1</sub>,...,''s''<sub>''k''</sub> are the
attribute names unique to ''S''. Furthermore, assume that the attribute names  ''x''<sub>1</sub>,...,''x''<sub>''m''</sub> are neither in ''R'' nor in ''S''. In a first step the common attribute names in ''S'' can be renamed:

{{NumBlk|:|<math>T = \rho_{x_1/c_1,\ldots,x_m/c_m}(S) = \rho_{x_1/c_1}(\rho_{x_2/c_2}(\ldots\rho_{x_m/c_m}(S)\ldots))</math>|{{EquationRef|2}}}}

Then we take the Cartesian product and select the tuples that are to be joined:

{{NumBlk|:|<math>P = \sigma_{c_1=x_1,\ldots,c_m=x_m}(R \times T) = \sigma_{c_1=x_1}(\sigma_{c_2=x_2}(\ldots\sigma_{c_m=x_m}(R \times T)\ldots))</math>|{{EquationRef|3}}}}

Finally we take a projection to get rid of the renamed attributes:

{{NumBlk|:|<math>U = \Pi_{r_1,\ldots,r_n,c_1,\ldots,c_m,s_1,\ldots,s_k}(P)</math>|{{EquationRef|4}}}}