10 Replies Latest reply on Oct 13, 2012 1:19 PM by Jonathan Lewis

# Is the inner join communtative?

My text book says that inner join is commutative: three tables A, B, C, so A join B join C equals A join C join B.

Below I have three tables and a query:
student(id, name, class_id)
class(class_id, teacher_id)
teacher(teacher_id, teach_name)

select * from student, class, teacher
where student.class_id=class.class_id and class.class_id=teacher.teacher_id

I inner join student table with class table, then with the teacher table. According to the communicativeness, I should be able to inner join student table with teacher table, then join the class table. But the student table and the teacher table do not have a common column, so they can not join. So is my text book wrong?

Thanks.
• ###### 1. Re: Is the inner join communtative?
I guess the right section is

Oracle Discussion Forums » Oracle Database » SQL and PL/SQL
• ###### 2. Re: Is the inner join communtative?
I think you are confusing the concept of commutative. It just means you can change the order of joins, but they still need to use the common columns to be an inner join. So you can have
A join B and B join C
or
C join B and B join A
etc.
• ###### 3. Re: Is the inner join communtative?
>
My text book says that inner join is commutative
>
The term 'commutative' is a mathematical term. I have never known it to be applied to joins.

Post the name, author and quote from the book.

In mathematics an operation is commutative if changing the order of the operands does not change the result.
But mathematically speaking there is only ONE result and their is no 'process'.

If the text book's use is to say that if all tables use inner joins to join to another table then changing the order of the tables does not change the 'result set' then that would be correct.
>
But the student table and the teacher table do not have a common column, so they can not join. So is my text book wrong?
>
Assuming the above is what the textbook means that commutative property for inner joins depends on being able to join any table to any other table properly and, as your example shows, your tables cannot be joined arbitrarily for the reason you stated. So the book isn't wrong, it just doesn't apply to your set of example tables.

The other assumption the book seems to make is that the result set is the only important thing.

But with queries, unlike mathematics, there is a process that is involved. The 'process' may change. Oracle may use different execution plans for different table orders. For example a nested loop might use a different driving table, different (or no) indexes, etc.

This can affect the performance of the query but will not affect the final result set.
>
select * from student, class, teacher
where student.class_id=class.class_id and class.class_id=teacher.teacher_id

I inner join student table with class table, then with the teacher table.
>
Not properly - you join the tables but on the wrong column. The class table should be joined to the teach table using the teacher_id column not the class_id column as you have it.
• ###### 4. Re: Is the inner join communtative?
user636837 wrote:
My text book says that inner join is commutative: three tables A, B, C, so A join B join C equals A join C join B.
Yes that is correct.
I inner join student table with class table, then with the teacher table. According to the communicativeness, I should be able to inner join student table with teacher table, then join the class table. But the student table and the teacher table do not have a common column, so they can not join. So is my text book wrong?
THere is a difference between the mathematical join (matrix or set operation) and the database join. The database join needs to know what are the tables and what is the join condition. THe pure mathematical expression A join B join C = B join A join C is true. But since the database join condition needs the join columns, you can't write them in any order. But this is a pure syntactical problem not a logical one. And only one that happens for ANSI joins.

For example you can do this:

non ansi join
``````select *
from student, class, teacher
where student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;

select * from teacher, student, class
where student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;``````
Both selects are identical and will give identical result sets.

The ANSI version is more difficult to write.
ansi join syntax
``````select *
from student
inner join class on student.student_id=class.student_id
inner join teacher on class.teacher_id=teacher.teacher_id
;

select *
from teacher
cross join student
inner join class on student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;``````
Maybe we need to add some parenthesis to make this work. But the concept is possible.
First a cartesian product is built using all students and all teachers. Then this product is inner joined with the class table to eliminate all entries that do not have a valid combination of teacher+student.

Why we get this syntax problem is because the ANSI join syntax in not purely communative.

This
``````select *
from student
inner join class on student.student_id=class.student_id ``````
can not be written like this:
``````select *
from class on student.student_id=class.student_id
inner join student``````
The order of the tables can change, but the join condition has to be always on the second element. But this is a syntax problem, not a logical problem. Logically the (inner) join is cummunative, syntactically not.

Edited by: Sven W. on Oct 12, 2012 5:18 PM

Edited by: Sven W. on Oct 12, 2012 5:21 PM - join columns changed to reflect a valid data model
• ###### 5. Re: Is the inner join communtative?
>
For example you can do this:

non ansi join

select *
from student, class, teacher
where student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;

select * from teacher, student, class
where student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;

Both selects are identical and will give identical result sets.
>
Well, of course they are since you didn't change the join at all. That doesn't demonstrate commutativity.
• ###### 6. Re: Is the inner join communtative?
Yes it does, the tables are listed in a different order. That's the essence of the concept: same results from a different order of elements.

Edit: I changed my mind, you are right, it should have also reordered the where clause.

I hadn't even considered the cartesian followed by filter example, that indeed illustrates the concept of getting the same results, though I wonder if it just shows equivalency rather than commutativeness - the joins are different, not just differently ordered.

Edited by: jgarry on Oct 12, 2012 10:11 AM
• ###### 7. Re: Is the inner join communtative?
rp0428 wrote:
>
select *
from student, class, teacher
where student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;

select * from teacher, student, class
where student.student_id=class.student_id and class.teacher_id=teacher.teacher_id;

Both selects are identical and will give identical result sets.
>
Well, of course they are since you didn't change the join at all. That doesn't demonstrate commutativity.
I think this is just a matter of wording.

In mathematics an operation is commutative if changing the order of the operands does not change the result.
The general logic (as described by the book) was:
A join B = B join A
Here A and B mean tables (well data sets). I changed the order of the tables to show that the join operation is commutative. I partially agree with you. The join condition should also have been reversed.

Strictly speaking the changed table order als ordered the columns in a different way, but that would be the projection part of the query. It doesn't influence the result set.

From a purist mathematical standpoint
A join B join C = C join B join A

can not be expressed purely using the communativ law. We also need to use the associative law for that.

Associative would mean:

(A join B) join C = A join (B join C)

For example I think a left outer join is not communative but is associative.

A left join B != B left join A

but isnt: (A left join B) left join C = A left join (B left join C)

Hm... it is a little late to think this though carefully. But have the strong feeling this fits.
• ###### 8. Re: Is the inner join communtative?
>
But have the strong feeling this fits.
>
Not suggesting it's necessary in this case but whenever I get a strong feeling about something Oracle-related I've learned to lie down until the feeling goes away. :D
• ###### 9. Re: Is the inner join communtative?
It seems like you would get the same result no matter what order you join the three tables together in.

If there is no predicate for the join you just get all the rows in one table combined with all the rows in the other.

I.e. all students and teachers where #rows=#students * #teachers

But then you join in the third table, classes, and you get the same number of rows, one per class.

- Bobby
• ###### 10. Re: Is the inner join communtative?
user636837 wrote:
My text book says that inner join is commutative: three tables A, B, C, so A join B join C equals A join C join B.
Your book appears to be mixing commutativity and associativity together.
Commutativity: is (A join B) = (B join A) ?
Associativity: is ((A join B) join C) = (A join (B join C)) ?

Since associativity holds, there is no ambiguity for the expression (A join B join C)
Hence
``````A join B join C = A join (B join C)   -- associativity
= A join (C join B)   -- commutativity
= A join C join B   -- associativity``````
As Sven W says, the logic is sound but the implementation of "join" may be flawed; (does a cartesian product in ANSI require you to state CROSS JOIN, or can the CROSS be implicit) and the performance of a query may be very bad if you force a join order that introduces a Cartesian join.

Reminder - this is all about inner joins.

Regards
Jonathan Lewis