-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Nov 13 '16 at 1:29
  • 1
    $\begingroup$ I think this question is more suitable for Computer Science. $\endgroup$ – Kaveh Nov 13 '16 at 1:30
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, you are right. Can you give the reasoning behind the formula $!(N-1)$? $\endgroup$ – Jingguo Yao Nov 12 '16 at 6:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Bjørn Kjos-Hanssen Nov 12 '16 at 7:00
0
$\begingroup$

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 $$(2n-3)!!=\prod_{i=1}^{n-1} 2i-1,$$

1, 1, 3, 15, 105, 945, 10395, 135135, ... (OEIS 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)

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.

$\endgroup$
  • $\begingroup$ From the slides: "N! ways to order joins (e.g., ABCD, ACBD, ….) (N-1)! plans per ordering (e.g., (((AB)C)D), ((AB)(CD), …) " $\endgroup$ – Bjørn Kjos-Hanssen Nov 12 '16 at 6:27
  • $\begingroup$ The number of plans for a fixed ordering is a Catalan number, not a factorial. $\endgroup$ – David Eppstein Nov 12 '16 at 17:04
  • $\begingroup$ 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". $\endgroup$ – Bjørn Kjos-Hanssen Nov 12 '16 at 17:58
  • $\begingroup$ 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)!. $\endgroup$ – Kaveh Nov 13 '16 at 19:40
  • $\begingroup$ @Kaveh: so you think AB and BA are different joins? $\endgroup$ – David Eppstein Nov 13 '16 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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