3

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)?

1 Answer 1

6

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.

8
  • Next, we apply conditions. The proof is not finished for associativity. The conditions are totally independent of attribute ordering, so I think we're done for proving commutativity across a single inner join. How do I prove that applying conditions on (A INNER JOIN B) then (Result INNER JOIN C) is equivalent to (B INNER JOIN C) then A INNER JOIN Result? I think I may need more assumptions about my join conditions.
    – joe55
    Jan 13, 2017 at 14:52
  • I haven't done it in detail, but define (A join B) join C, and compare it to how you define A join (B join C). (A join B) join C = { (a1 .. an b1 .. bn) | ___ } join C = { (a1.. cn) | ___ }. Do the same for A join (B join C). You will have (condAB) and (condBC), and you will probably need to use commutativity and associativity of boolean and.
    – joanolo
    Jan 13, 2017 at 15:41
  • So, conditions AC may exist. I think I must assume that conditions only depend on individual attribute values and are not derived from some aggregate measures (e.g. ON b_2 = sum(a_1)). Otherwise, we definitely lose associativity. If so, can I wait to apply them until we have the full cartesian product A x B x C? I'm trying to see how to do that.
    – joe55
    Jan 13, 2017 at 16:49
  • Good question. I've done joins with various operators and functions, but I am pretty sure I've ever done them with aggregates. I'm not sure how I would join with an aggregate (have you though of a realistic SQL example?). I don't think SQL aggregates are part of RT. This is an extension, in the same way that the order of attributes in a SELECT statement, having duplicate rows, or having an ORDER BY are. So, I would start by assuming that your conditions are f(attributes of rows), which is what relational theory does.
    – joanolo
    Jan 13, 2017 at 17:02
  • Ok, that makes sense. I think we need to actually restrict the conditions to f(attributes of a single Cartesian product result row), so that a row is never compared to some quantity dependent on another row in the final, full Cartesian product result set. But, if we make that restriction on conditions, still, I don't know why we are allowed to apply the conditions after the full cartesian product of N INNER-JOINed tables instead of at each step. Do you know why?
    – joe55
    Jan 13, 2017 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.