This discussion is archived
10 Replies Latest reply: Oct 13, 2012 6:19 AM by Jonathan Lewis RSS

Is the inner join communtative?

639840 Newbie
Currently Being Moderated
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?
    Osama_Mustafa Oracle ACE
    Currently Being Moderated
    I guess the right section is


    Oracle Discussion Forums » Oracle Database » SQL and PL/SQL
  • 2. Re: Is the inner join communtative?
    jgarry Guru
    Currently Being Moderated
    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?
    rp0428 Guru
    Currently Being Moderated
    >
    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?
    Sven W. Guru
    Currently Being Moderated
    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?
    rp0428 Guru
    Currently Being Moderated
    >
    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?
    jgarry Guru
    Currently Being Moderated
    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?
    Sven W. Guru
    Currently Being Moderated
    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.

    You already gave the description:
    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?
    rp0428 Guru
    Currently Being Moderated
    >
    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?
    Bobby Durrett Explorer
    Currently Being Moderated
    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?
    Jonathan Lewis Oracle ACE Director
    Currently Being Moderated
    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

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points