<p>I guess $((AB)(CD))$ is actually two ways, because you could do either $(AB)$ or $(CD)$ first.</p>

CC BY-SA 3.0
2016-11-12T06:54:58.433Z
Yes, you are right. Can you give the reasoning behind the formula $!(N-1)$?
Jingguo Yao
CC BY-SA 3.0
2016-11-12T07:00:31.057Z
Yes, every join occurs at one of the positions between two letters, and there are $N-1$ positions that are between two of $N$ symbols. And $(N-1)!$ is the number of orderings of $N-1$ things.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2016-11-12T05:51:18.843Z
2016-11-12T05:51:18.843Z
Bjørn Kjos-Hanssen
<p>Aren't you missing (AC)B?</p>

<p>The number of ways of completely parenthesizing $n$ objects (where the parenthesization matters but the pairings are commutative) are given by the <a href="https://en.wikipedia.org/wiki/Double_factorial" rel="nofollow noreferrer">odd double factorial</a>
$$(2n-3)!!=\prod_{i=1}^{n-1} 2i-1,$$</p>

<p>1, 1, 3, 15, 105, 945, 10395, 135135, ... (<a href="http://oeis.org/A001147" rel="nofollow noreferrer">OEIS A001147</a>).</p>

<p>But of course for an actual database many of those won't make sense as a join, because the relations won't share a column. Are you looking for the number of different choices when you haven't yet determined the schema (for which the answer is the one above) or for when you have a fixed schema (in which case it would depend on the schema)?</p>

<p>Update: it seems that what is being asked is not just the parenthesization but then the sequence of operations. If the joins are non-commutative, then the $n!(n-1)!$ answer would be correct: you have $n!$ ways of placing the tables into a sequence, after which a parenthesization and sequence is determined uniquely by a permutation on the gaps between consecutive items in the sequence. Each gap describes a pair of things to be joined (input tables, or results of prior joins) and replaces them by their join.</p>

<p>However, I still maintain that joining is generally a commutative operation, so that $AB=BA$. With the above formula, each sequence of $n-1$ operations is counted exactly $2^{n-1}$ times, once for each way of swapping the arguments for each operation. So the actual count should be $n!(n-1)!/2^{n-1}$.</p>

<p>This gives the sequence</p>

<p>1, 1, 3, 18, 180, 2700, 56700, 1587600, 57153600, ... (<a href="http://oeis.org/A006472" rel="nofollow noreferrer">OEIS A001147</a>)</p>

<p>For instance, there are 18 sequences of operations on four items. The first pair to join is one of the six pairs AB,AC,AD,BC,BD,BD, and they're all symmetric, so let's say we start with AB. Then there are three sequences that start this way: ((AB)C)D, ((AB)D)C, and (AB)(CD). Each of the other five starting pairs also belongs to three sequences, giving 18 total.</p>

CC BY-SA 3.0
2016-11-12T06:27:04.613Z
From the slides: "N! ways to order joins (e.g., ABCD, ACBD, ….)
(N-1)! plans per ordering (e.g., (((AB)C)D), ((AB)(CD), …)
"
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2016-11-12T17:04:18.280Z
The number of plans for a fixed ordering is a Catalan number, not a factorial.
David Eppstein
CC BY-SA 3.0
2016-11-12T17:58:32.773Z
Depends what we mean by plan. Does order matter? "Win the presidency, then make America great again" is not the same plan as "Make America great again, then win the presidency".
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2016-11-13T19:40:27.113Z
I think what they mean is much simpler: they are not considering concurrent joins, it is ordering of (n-1) joins in a sequence which is obviously (n-1)!.
Kaveh
CC BY-SA 3.0
2016-11-13T19:49:16.410Z
@Kaveh: so you think AB and BA are different joins?
David Eppstein
CC BY-SA 3.0
2016-11-13T20:07:01.683Z
I think the order of A,B,C,... is fixed (the first n!), the (n-1)! is the order of _performing_ the (n-1) joins. E.g. A1B2C or A2B1C. If they allowed performing the joins concurrently the number would be different, which would again be different from counting different ways of parenthesizing the operations. I think the slide just wants to say that there are too many possibilities for brute-force is not careful in defining what is the space of solutions and uses parenthesis for the example which makes it confusing.
Kaveh
CC BY-SA 3.0
2016-11-13T20:11:49.167Z
ps: looking at the Slinger et. al paper "[Access
path selection in a relational database management system](https://doi.org/10.1145/582095.582099)" it seems the space is closer to parenthesizing.
Kaveh
CC BY-SA 3.0
2016-11-12T06:03:15.640Z
2016-11-13T00:28:37.567Z
2016-11-13T00:28:37.567Z
David Eppstein
<p>On page 2 of <a href="http://db.csail.mit.edu/6.830/lectures/selinger.ppt" rel="nofollow noreferrer">http://db.csail.mit.edu/6.830/lectures/selinger.ppt</a>, there is the following text:</p>
<blockquote>
<p>How to order a series of N joins, e.g., <br>
A.a = B.b AND A.c = D.d AND B.e = C.f</p>
<p><span class="math-container">$N!$</span> ways to order joins (e.g., ABCD, ACBD, ….)<br>
<span class="math-container">$(N-1)!$</span> plans per ordering (e.g., (((AB)C)D), ((AB)(CD), …)<br>
Multiple implementations (e.g., hash, nested loops, etc)</p>
</blockquote>
<p>The statement &quot;<span class="math-container">$(N-1)!$</span> plans per ordering&quot; does not hold.</p>
<p>For <span class="math-container">$N = 2$</span>, there is one way for join: (AB). The statement holds.</p>
<p>For <span class="math-container">$N = 3$</span>, there are two ways for join: ((AB)C), (A(BC)). The statement also holds.</p>
<p>But for <span class="math-container">$N = 4$</span>, there are 5 ways for join: ((AB)(CD)), (((AB)C)D), ((A(BC))D), (A(B(CD))) and (A((BC)D)). But <span class="math-container">$(4-1)! = 6 \ne 5$</span>.</p>
<p>Is the statement wrong? If the statement is wrong, is there a correct formula to compute the number of the plans per ordering?</p>

CC BY-SA 3.0
2016-11-13T01:29:49.680Z
there are n-1 join operations that have to be performed. They can be performed in arbitrary order so the answer is n-1 factorial.
Kaveh
CC BY-SA 3.0
2016-11-13T01:30:21.837Z
I think this question is more suitable for [cs.se].
Kaveh
<db.databases>
Are there (N-1)! ways to order joins?
Jingguo Yao
# Are there (N-1)! ways to order joins?

(Asked by: username_0 on 2016-11-12)

On page 2 of <http://db.csail.mit.edu/6.830/lectures/selinger.ppt>, there is the following text:

> How to order a series of N joins, e.g.,   
> A.a = B.b AND A.c = D.d AND B.e = C.f
>
> $N!$ ways to order joins (e.g., ABCD, ACBD, ….)  
> $(N-1)!$ plans per ordering (e.g., (((AB)C)D), ((AB)(CD), …)  
> Multiple implementations (e.g., hash, nested loops, etc)

The statement "$(N-1)!$ plans per ordering" does not hold.

For $N = 2$, there is one way for join: (AB). The statement holds.

For $N = 3$, there are two ways for join: ((AB)C), (A(BC)). The statement also holds.

But for $N = 4$, there are 5 ways for join: ((AB)(CD)), (((AB)C)D), ((A(BC))D), (A(B(CD))) and (A((BC)D)). But $(4-1)! = 6 \ne 5$.

Is the statement wrong? If the statement is wrong, is there a correct formula to compute the number of the plans per ordering?

**Tags:** db.databases

> **Comments:**
> **username_1**: there are n-1 join operations that have to be performed. They can be performed in arbitrary order so the answer is n-1 factorial.  
> **username_1**: I think this question is more suitable for [cs.se].  

---

## 2 answers

### Answer by username_2 on 2016-11-12. Score: 3 | Accepted answer

I guess $((AB)(CD))$ is actually two ways, because you could do either $(AB)$ or $(CD)$ first.

> **Comments:**
> **username_0**: Yes, you are right. Can you give the reasoning behind the formula $!(N-1)$?  
> **username_2**: Yes, every join occurs at one of the positions between two letters, and there are $N-1$ positions that are between two of $N$ symbols. And $(N-1)!$ is the number of orderings of $N-1$ things.  

---

### Answer by username_3 on 2016-11-12. Score: 0

Aren't you missing (AC)B?

The number of ways of completely parenthesizing $n$ objects (where the parenthesization matters but the pairings are commutative) are given by the [odd double factorial](https://en.wikipedia.org/wiki/Double_factorial)
$$(2n-3)!!=\prod\_{i=1}^{n-1} 2i-1,$$

1, 1, 3, 15, 105, 945, 10395, 135135, ... ([OEIS A001147](http://oeis.org/A001147)).

But of course for an actual database many of those won't make sense as a join, because the relations won't share a column. Are you looking for the number of different choices when you haven't yet determined the schema (for which the answer is the one above) or for when you have a fixed schema (in which case it would depend on the schema)?

Update: it seems that what is being asked is not just the parenthesization but then the sequence of operations. If the joins are non-commutative, then the $n!(n-1)!$ answer would be correct: you have $n!$ ways of placing the tables into a sequence, after which a parenthesization and sequence is determined uniquely by a permutation on the gaps between consecutive items in the sequence. Each gap describes a pair of things to be joined (input tables, or results of prior joins) and replaces them by their join.

However, I still maintain that joining is generally a commutative operation, so that $AB=BA$. With the above formula, each sequence of $n-1$ operations is counted exactly $2^{n-1}$ times, once for each way of swapping the arguments for each operation. So the actual count should be $n!(n-1)!/2^{n-1}$.

This gives the sequence

1, 1, 3, 18, 180, 2700, 56700, 1587600, 57153600, ... ([OEIS A001147](http://oeis.org/A006472))

For instance, there are 18 sequences of operations on four items. The first pair to join is one of the six pairs AB,AC,AD,BC,BD,BD, and they're all symmetric, so let's say we start with AB. Then there are three sequences that start this way: ((AB)C)D, ((AB)D)C, and (AB)(CD). Each of the other five starting pairs also belongs to three sequences, giving 18 total.

> **Comments:**
> **username_2**: From the slides: "N! ways to order joins (e.g., ABCD, ACBD, ….) (N-1)! plans per ordering (e.g., (((AB)C)D), ((AB)(CD), …) "  
> **username_3**: The number of plans for a fixed ordering is a Catalan number, not a factorial.  
> **username_2**: Depends what we mean by plan. Does order matter? "Win the presidency, then make America great again" is not the same plan as "Make America great again, then win the presidency".  
> **username_1**: I think what they mean is much simpler: they are not considering concurrent joins, it is ordering of (n-1) joins in a sequence which is obviously (n-1)!.  
> **username_3**: @username_1: so you think AB and BA are different joins?  
> **username_1**: I think the order of A,B,C,... is fixed (the first n!), the (n-1)! is the order of _performing_ the (n-1) joins. E.g. A1B2C or A2B1C. If they allowed performing the joins concurrently the number would be different, which would again be different from counting different ways of parenthesizing the operations. I think the slide just wants to say that there are too many possibilities for brute-force is not careful in defining what is the space of solutions and uses parenthesis for the example which makes it confusing.  
> **username_1**: ps: looking at the Slinger et. al paper "[Access path selection in a relational database management system](https://doi.org/10.1145/582095.582099)" it seems the space is closer to parenthesizing.  

---

