Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a database textbook which says the following:

enter image description here

There is no further explanation or elaboration for how this formula was arrived at. In attempting to derive it myself, I come up with something different. For example:

For N = 2 (two tables A and B), I count 2 ways to join them:

A join B
B join A

Now for N = 3 (three tables A, B, C), I count 12 ways to join them, which agrees with the text. The way I get this is by considering that after the first join (out of the two joins that must be performed total in a 3-table situation), there will be 2 tables remaining, and in that case we've already seen there are 2 options. So we need to find out how many different options we have for this "first join" and then multiply that by 2. There are 6 "first step" options (enumerated below), and 6 x 2 = 12.

A join B
A join C
B join A
B join C
C join A
C join B

Now, for N = 4 (four tables A, B, C, D), I count 144 ways to join, which does not agree with the 120 quoted in the text. As before, my strategy is to find the number of ways to make the "first join" and then multiply that by the N = 3 option count (12), since at this point 3 tables and 2 joins will remain. I count 12 options for the "first join" which leads to 12 x 12 = 144.

A join B
A join C
A join D
B join A
B join C
B join D
C join A
C join B
C join D
D join A
D join B
D join C

I am assuming the text is correct and I am mistaken. Where is my error?

share|improve this question

migrated from stackoverflow.com Mar 13 '13 at 14:20

This question came from our site for professional and enthusiast programmers.

    
How are joins defined in your case? Normally, the total number of join orders is N! if there are no further constraints on order. –  usr Mar 10 '13 at 22:26
    
@usr I'm not sure what you mean by join definition, other than the obvious: a binary operation between 2 tables that selects a subset of a cross product satisfying some predicate. The text I pasted is from a chapter on dynamic programming cost-based query optimization, and if it helps, the sentence that proceeds it reads "For the sake of simplicity when discussing dynamic programming, let’s consider the case of joining N relations together in an N-way join, that is, “R1 JN R2 . . . JN RN−1 JN RN.” –  The111 Mar 10 '13 at 22:32

1 Answer 1

My first suggestion would have been to better ask this question on http://math.stackexchange.com/ , but then I just spent some time researching a possible answer. By the way, I found the original quote on Google Books, and also the referenced paper by Selinger 79.

Of course, the factorial indicates the formular describes a problem in combinatorics, but I was intrigued by the expression (2*(n-1))! as I could not figure out what the 2*(n-1) would refer to.

If we take n as the number of tables ("relations" in database theory language), then n-1 is the number of JOINs. But how should the double of the number of JOINS be relevant for the result?

As it turned out, the formula (2*n)!/n! is related to Catalan numbers (see section Quadruple factorial):

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects.

From the application

Cn is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator)

I conclude, that if we take a JOIN as binary operator, then the number of alternatives in OP is Cn * number of combinations of tables.

share|improve this answer
    
Wow. Good info, albeit maybe deeper than my brain can go at the moment. Thanks for the links though, I will try to digest them. I'm not sure I entirely understand the formula in your conclusion... what does that give you for N = 4? Maybe I will take your advice and see if I can get this migrated to Math. –  The111 Mar 11 '13 at 1:16
    
Great answer. Then the joins in the example given by the OP are all ordered (no commutativity). If they were not ordered (which is usually the case), N! would be the formula. –  usr Mar 11 '13 at 10:47
    
N! is the number of permutations. The Catalan number, from what I understand, gives the number of associative combinations (e.g. A JOIN (B JOIN C) vs. (A JOIN B) JOIN C). The query optimizer uses table statistics to determine which associative combination is the most optimal to compute. This seems similar to matrix multiplication. –  devio Mar 11 '13 at 10:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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