Proof that Inner Join is Commutative

join;relational-algebrarelational-theoryrelations

I'm trying to prove to myself that the order of inner joins doesn't matter, but, in an abstract sense, I'm coming up with nothing.

How would one go about proving that the order of a set of INNER JOINs that are executed to turn many tables into a single table does not affect the result set (i.e., prove commutativity and associativity of the INNER JOIN operation)?

Best Answer

An inner join is the subset of rows from the cartesian product where a certain condition is true. Although the cartesian product is not commutative (nor associative), it is with regard to relational theory.

It is so because the order of attributes doesn't matter in relational theory. If A and B are tables, then:

A x B = { (a1, a2, .., an, b1, b2, .. bn) | (a1..an) € A and (b1..bn) € B}
      = { (b1, b2, .., bn, a1, a2, .. an) | (a1..an) € A and (b1..bn) € B}  ((1))
      = { (b1, b2, .., bn, a1, a2, .. an) | (b1..bn) € B and (a1..an) € A}  ((2))
      = B x A                                                               ((3))

((1)) because the order of attributes doesn't matter
((2)) because the logical and is commutative
((3)) by definition of B x A

The condition for choosing which elements of the cartesian must be selected will be the same no matter the JOIN order, and as such, doesn't influence this reasoning.

The proof for associativity follows the same line of reasoning.

Related Question