## New SQL Puzzle

June 13th, 2012 — ddelmoliSorry for the drought — to keep everyone’s mind fresh, how about a little puzzle?

Use SQL to create a symmetric Pascal matrix, with the output being (i,j,v). So that a Pascal matrix of size 4 would end up as:

1,1,1

2,1,1

3,1,1

4,1,1

1,2,1

2,2,2

3,2,3

4,2,4

1,3,1

2,3,3

3,3,6

4,3,10

1,4,1

2,4,4

3,4,10

4,4,20

Try to stay with ANSI SQL 2008 if possible — bailing out to other languages and functions is discouraged

Efficiency is an interesting idea here, as it’s pretty easy to do this by brute force calculations of factorials for every entry — but where’s the fun in that?

Extra credit for solutions which can take in the matrix size as some sort of parameter.

June 14th, 2012 at 7:00 am

I put together a solution using WITH blocks and Oracle specific syntax, so a solution is possible using just SQL (but I am not sure if that Oracle specific syntax qualifies as ANSI SQL 2008).

This is my output:

I J V

– — —-

1 1 1

2 1 1

3 1 1

4 1 1

1 2 1

2 2 2

3 2 3

4 2 4

1 3 1

2 3 3

3 3 6

4 3 10

1 4 1

2 4 4

3 4 10

4 4 20

Any interest in seeing the Oracle specific code?

June 14th, 2012 at 7:40 am

Charles, sure! WITH blocks aren’t Oracle-specific (I was able to run my solution in Postgres and Oracle), so I’d love to see what you came up “with”.

June 14th, 2012 at 8:21 am

I have a degree in mathematics, but that degree is very, very rusty. Based on the provided link, we are trying to produce an array like the following, where the value in a cell in the array is the sum of the value immediately above and immediately to the left:

1 1 1 1 1

1 2 3 4 5

1 3 6 10 15

1 4 10 20 35

1 5 15 35 70

The first rows have the following values:

1^0 + 2^0

1^0 + 2^0 + 3^0

1^0 + 2^0 + 3^0 + 4^0

1^0 + 2^0 + 3^0 + 4^0 + 5^0

The second row has the following values:

1^0 + 2^0 + 1^0

1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 = 1 * 3^0 + 2 * 2^0 + 3 * 1^0

1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 = 1 * 4^0 + 2 * 3^0 + 3* 2^0 + 4 * 1^0

1^0 + 2^0 + 3^0 + 4^0 + 5^0 + 1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 = 1 * 5^0 + 2 * 4^0 + 3 * 3^0 + 4 * 2^0 + 5 * 1^0

The third row:

1^0 + 2^0 + 1^0 + 1^0

1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 1^0 + 1^0 = 1 * 3^0 + 3 * 2^0 + 6 * 1^0

1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 1^0 + 1^0 = 1 * 4^0 + 3 * 3^0 + 6 * 2^0 + 10 * 1^0

1^0 + 2^0 + 3^0 + 4^0 + 5^0 + 1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 1^0 + 1^0

Now we can just… cheat and look at the formula from the article that you provided:

(i + j – 2)! / ((i – 1)! * (j – 1)!)

! is short for factorial

4! = 4 * 3 * 2 * 1

3! = 3 * 2 * 1

2! = 2 * 1

1! = 1

Calculating the factorial is a bit of a challenge. The SUM analytic function can be used to generate running sums of a column, but there is no equivalent for running products of a column.

If we calculate the natural log of a column value, generate a running sum of those natural log values, and then generate the anti-log, we can essentially generate a running product (factorial) for a column:

WITH

FACTORIAL AS

(SELECT /*+ MATERIALIZE */

N,

EXP(SUM(LN(N)) OVER (ORDER BY N)) FACTORIAL

FROM

(SELECT

ROWNUM N,

LN(ROWNUM) RNL

FROM

DUAL

CONNECT BY

LEVEL<=20))

SELECT

N,

FACTORIAL F

FROM

FACTORIAL;

N F

– ———-

1 1

2 2

3 6

4 24

5 120

6 720

7 5040

8 40320

9 362880

10 3628800

11 39916800

12 479001600

13 6227020800

14 8.7178E+10

15 1.3077E+12

16 2.0923E+13

17 3.5569E+14

18 6.4024E+15

19 1.2165E+17

20 2.4329E+18

One problem is that with the formula (i + j – 2)!, we could very well need to calculate 0!, which is defined as 1. To accomplish this, we need to add the following inside the WITH block:

UNION ALL

SELECT

0 N,

1 FACTORIAL

FROM

DUAL

Now it is just a matter of defining how large of an array is needed, performing a Cartesian join to achieve the correct number of rows (I * J), and placing the factorial values where necessary:

WITH

FACTORIAL AS

(SELECT /*+ MATERIALIZE */

N,

EXP(SUM(LN(N)) OVER (ORDER BY N)) FACTORIAL

FROM

(SELECT

ROWNUM N,

LN(ROWNUM) RNL

FROM

DUAL

CONNECT BY

LEVEL<=20)

UNION ALL

SELECT

0 N,

1 FACTORIAL

FROM

DUAL),

I AS

(SELECT /*+ MATERIALIZE */

ROWNUM I

FROM

DUAL

CONNECT BY

LEVEL<=4),

J AS

(SELECT /*+ MATERIALIZE */

ROWNUM J

FROM

DUAL

CONNECT BY

LEVEL<=4)

SELECT

I.I,

J.J,

F1.FACTORIAL / (F2.FACTORIAL * F3.FACTORIAL) V

FROM

FACTORIAL F1,

FACTORIAL F2,

FACTORIAL F3,

I,

J

WHERE

F1.N=(I.I + J.J – 2)

AND F2.N=(I.I – 1)

AND F3.N=(J.J – 1)

ORDER BY

J.J,

I.I;

June 14th, 2012 at 2:36 pm

[...] Dominic’s challenge probably would not be much of a challenge if we could just type in formulas like the above into a SQL statement. Give his challenge a try to see if you are able to derive a unique solution to the problem. I probably spent a couple of minutes (maybe 60 seconds with the help of copy and paste) creating the above example using Microsoft Excel, but spent a couple of hours trying to produce a solution that worked using SQL. [...]

June 14th, 2012 at 6:41 pm

A PostgreSQL approach – Mixing analytic functions and recursive subquery factoring. http://rafudb.blogspot.fi/2012/06/pascal-matrix.html

June 14th, 2012 at 8:02 pm

Nice one Timo — glad to see another approach!

June 15th, 2012 at 3:34 am

select i

, j

, ( select exp( sum( ln( level ) ) ) from dual connect by level <= i + j – 2 )

/ ( select exp( sum( ln( level ) ) ) from dual connect by level <= i – 1 )

/ ( select exp( sum( ln( level ) ) ) from dual connect by level <= j – 1 ) v

from ( select mod( level – 1, n ) + 1 i

, ceil( level / n ) j

from ( select 8 n from dual )

connect by level <= n * n

)

June 15th, 2012 at 7:59 am

Anton, good one — I particularly like the single reference to the size of the array. And so far I’ve been impressed with the use of the exp(sum(ln())) construct to calculate the factorials.

June 15th, 2012 at 8:30 am

I think the statement below does the trick:

with r as (select level nr from dual connect by level <= 9 ) , z as (select r.nr row_nr , c.nr col_nr from r r , r c ) , p as (select * from z model dimension by (row_nr, col_nr) measures (cast(null as number) new_val) rules ( new_val[any, any] order by row_nr, col_nr = greatest(case when new_val[cv()-1, cv()] is null then 0 else new_val[cv()-1, cv()] end + case when new_val[cv(),cv()-1] is null then 0 else new_val[cv(),cv()-1] end ,1 ) ) ) select * from p pivot (sum(new_val) for col_nr in (1,2,3,4,5,6,7,8,9)) order by row_nr –, col_nr ;

The pivot is just for formatting the output. If you comment it out, the fixed number for the matrix size can be made dynamic.

June 15th, 2012 at 8:55 am

I admit this is probably pure Oracle (I have no idea which other databases might support the MODEL clause), but it was fun to make so I might as well share it

SQL> variable matrixsize number

SQL>

SQL> begin

2 :matrixsize := 4;

3 end;

4 /

PL/SQL procedure successfully completed.

SQL>

SQL> select

2 i, j, v

3 from dual

4 model

5 dimension by (1 i, 1 j)

6 measures (1 v)

7 rules automatic order (

8 v[for i from 2 to :matrixsize increment 1, 1] = 1,

9 v[1, for j from 2 to :matrixsize increment 1] = 1,

10 v[for i from 2 to :matrixsize increment 1,

11 for j from 2 to :matrixsize increment 1

12 ] = v[cv(i)-1,cv(j)] + v[cv(i),cv(j)-1]

13 )

14 order by

15 i, j;

I J V

———- ———- ———-

1 1 1

1 2 1

1 3 1

1 4 1

2 1 1

2 2 2

2 3 3

2 4 4

3 1 1

3 2 3

3 3 6

3 4 10

4 1 1

4 2 4

4 3 10

4 4 20

16 rows selected.

June 15th, 2012 at 10:06 am

Here is another possible solution that uses SYS_CONNECT_BY_PATH to create formulas and XMLQUERY to calculate the value of those formulas to generate the factorial values.

First, the formulas are built:

SELECT

ROWNUM N,

FF

FROM

(SELECT

’1′||SYS_CONNECT_BY_PATH(ROWNUM,’ * ‘) FF

FROM

DUAL

CONNECT BY

LEVEL<=8

ORDER BY 1);

N FF

- ———————————

1 1 * 1

2 1 * 1 * 2

3 1 * 1 * 2 * 3

4 1 * 1 * 2 * 3 * 4

5 1 * 1 * 2 * 3 * 4 * 5

6 1 * 1 * 2 * 3 * 4 * 5 * 6

7 1 * 1 * 2 * 3 * 4 * 5 * 6 * 7

8 1 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8

As shown above, I am only planning to calculate through 8!, but that will later be changed to 20!.

Next, the value of the formulas are calculated:

SELECT

ROWNUM N,

XMLQUERY((FF) RETURNING CONTENT).GETNUMBERVAL() FACTORIAL

FROM

(SELECT

’1′||SYS_CONNECT_BY_PATH(ROWNUM,’ * ‘) FF

FROM

DUAL

CONNECT BY

LEVEL<=8

ORDER BY 1);

N FACTORIAL

- ———-

1 1

2 2

3 6

4 24

5 120

6 720

7 5040

8 40320

The above SQL statement does not calculate 0!, so that problem will be handled later by a DECODE statement.

The following will be used to derive the i and j values for an 8 x 8 matrix:

SELECT

MOD(ROWNUM-1,8)+1 I,

TRUNC((ROWNUM-1)/8)+1 J

FROM

DUAL

CONNECT BY

LEVEL <= 8 * 8;

The final query uses two WITH block subqueries, and scalar subqueries to pull the correct factorial value for the calculation:

WITH

FACTORIAL AS

(SELECT /*+ MATERIALIZE */

ROWNUM N,

XMLQUERY((FF) RETURNING CONTENT).GETNUMBERVAL() FACTORIAL

FROM

(SELECT

’1′||SYS_CONNECT_BY_PATH(ROWNUM,’ * ‘) FF

FROM

DUAL

CONNECT BY

LEVEL<=20

ORDER BY 1)),

NUMBERS AS

(SELECT

MOD(ROWNUM-1,8)+1 I,

TRUNC((ROWNUM-1)/8)+1 J

FROM

DUAL

CONNECT BY

LEVEL <= 8 * 8)

SELECT

N.I,

N.J,

DECODE((N.I + N.J – 2),0,1,

(SELECT

F.FACTORIAL

FROM

FACTORIAL F

WHERE

F.N=(N.I + N.J – 2))) /

DECODE((N.I – 1),0,1,

(SELECT

F.FACTORIAL

FROM

FACTORIAL F

WHERE

F.N=(N.I – 1))) /

DECODE((N.J – 1),0,1,

(SELECT

F.FACTORIAL

FROM

FACTORIAL F

WHERE

F.N=(N.J – 1))) V

FROM

NUMBERS N;

I J V

– — —–

1 1 1

2 1 1

3 1 1

4 1 1

5 1 1

6 1 1

7 1 1

8 1 1

1 2 1

2 2 2

3 2 3

4 2 4

5 2 5

6 2 6

7 2 7

8 2 8

1 3 1

2 3 3

3 3 6

4 3 10

5 3 15

6 3 21

7 3 28

8 3 36

1 4 1

2 4 4

3 4 10

4 4 20

5 4 35

6 4 56

7 4 84

8 4 120

1 5 1

2 5 5

3 5 15

4 5 35

5 5 70

6 5 126

7 5 210

8 5 330

1 6 1

2 6 6

3 6 21

4 6 56

5 6 126

6 6 252

7 6 462

8 6 792

1 7 1

2 7 7

3 7 28

4 7 84

5 7 210

6 7 462

7 7 924

8 7 1716

1 8 1

2 8 8

3 8 36

4 8 120

5 8 330

6 8 792

7 8 1716

8 8 3432

June 16th, 2012 at 6:46 pm

with pascal( i, j, v, n, pv )

as ( select 1, 1, 1, 8, mdsys.sdo_numtab( 1 )

from dual

union all

select case when i = n then 1 else i + 1 end

, case when i = n then j + 1 else j end

, case when i = n or j = 1 then 1 else v + ( select column_value from table( pv ) where rownum < 2 ) end

, n

, case when cardinality( pv ) = n then pv multiset except ( select mdsys.sdo_numtab( column_value ) from table( pv ) where rownum < 2 ) else pv end multiset union mdsys.sdo_numtab( case when i = n or j = 1 then 1 else v + ( select column_value from table( pv ) where rownum < 2 ) end )

from pascal

where i < n or j < n

)

select i, j, v

from pascal

June 16th, 2012 at 7:35 pm

[...] Comments anton on New SQL PuzzleCharles Hooper on New SQL PuzzleKim Berg Hansen on New SQL [...]

June 20th, 2012 at 6:56 am

[...] been impressed with the solutions to my little problem of generating a symmetric Pascal matrix using SQL. Charles Hooper in particular has provided [...]