June 14, 2012
Dominic Delmolino put together a very interesting challenge. The challenge is to produce something called a Pascal matrix using Oracle Database… more specifically, just SQL. I had a vague recollection of Pascal matrixes when I read Dominic’s challenge. Basically, the goal is to create a matrix similar to the following:
The rule for generating the matrix is simply that a cell’s value is the sum of the value in the cell that is immediately to the left plus the value in the cell that is immediately above. Sounds easy, right?
If we were just working in Microsoft Excel (or some other spreadsheet package), we could do something like this to quickly create the matrix:
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.
——
Part 2 of the challenge.
Take a look at the bullet point items in this blog article about NULL values in table’s columns, in particular the first three large bullet point items. Do you agree or disagree with the statements, and why?
Easy way is this
select
col_1,
col_2,
col_3,
col_4,
col_5,
col_6,
col_7,
col_8
from
dual connect by level 1] = col_1[cv()] + col_2[cv(lev) – 1] ,
col_3[lev > 1] = col_2[cv()] + col_3[cv(lev) – 1] ,
col_4[lev > 1] = col_3[cv()] + col_4[cv(lev) – 1] ,
col_5[lev > 1] = col_4[cv()] + col_5[cv(lev) – 1] ,
col_6[lev > 1] = col_5[cv()] + col_6[cv(lev) – 1] ,
col_7[lev > 1] = col_6[cv()] + col_7[cv(lev) – 1] ,
col_8[lev > 1] = col_7[cv()] + col_8[cv(lev) – 1]
);
Raj,
Thanks for posting, but it appears that a portion of your SQL statement disappeared. Less than and greater than signs in comments can cause problems, because those characters are used to denote formatting keywords on web pages. I am interested in seeing the full SQL statement, please repost. See the note at the very bottom of the blue section at the right regarding what substitutions needs to be performed to include less than and greater than signs in comments. Thanks.
P.S. Please also post your solution at http://www.oraclemusings.com/?p=221 – you will need to make the same replacements for less than and greater than signs on that site.
Hi Charles,
Apologies. I didn’t read the guidelines before posting the comments. My bad. I think I got it right this time.
Thanks
Raj
Raj,
That is impressive.
I have not worked with the model clause, but had hoped that someone would post an example using that clause. It appears that the model clause is quite powerful, allowing the specification of formulas that are similar to the formulas that I used in Microsoft Excel at the start of this article.
Thanks again for posting the example.
There are clearly some very creative solutions to this problem, as seen on the other blog.
Formatting of code sections is a bit of a problem, so I thought that I would share my two solutions here.
The first solution that I created:
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:
The first rows have the following values:
The second row has the following values:
The third row:
Now we can just… cheat and look at the formula from the article that you provided:
! is short for factorial
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:
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:
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:
The second solution that I created:
Here is another possible solution that uses SYS_CONNECT_BY_PATH to create formulas and XMLQUERY to calculate the value of those formulas.
First, the formulas are built:
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:
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:
The final query uses two WITH block subqueries, and scalar subqueries to pull the correct factorial value for the calculation:
[…] with the solutions to my little problem of generating a symmetric Pascal matrix using SQL. Charles Hooper in particular has provided some very nice commentary on the problem, complete with diagrams and 2 alternative […]
select * from (
select *
from
(select level x from dual connect by level<=8),
(select level y from dual connect by level1, y>1] = s[cv(x)-1, cv()] + s[cv(), cv(y)-1]
)
)
pivot (max(s) for x in (1,2,3,4,5,6,7,8))
order by 1
Mrpy,
An interesting looking SQL statement. Unfortunately, it appears that part of your SQL statement disappeared:
Unfortunately, less than and greater than signs are HTML formatting keywords. As such, it is necessary to replace less than (<) and greater than (>) signs in comments with the appropriate HTML equivalent – see the bottom of the blue section at the right.
I am looking forward to seeing this full SQL statement.
[…] with the solutions to my little problem of generating a symmetric Pascal matrix using SQL. Charles Hooper in particular has provided some very nice commentary on the problem, complete with diagrams and 2 alternative […]
Hi,
Here is another solutionusing the model clause:
The result is below:
Regards,
Peter
Peter,
Sorry for the delay in responding. Very nice solution with the MODEL clause. I suspected that there was an elegant solution to the problem using the MODEL clause, but I have not worked with it often enough to put the solution together from the beginning to the end.
Neat post! 🙂 I was able to solve it in a few minutes with this query (using postgres):
select x,y,factorial(x+y-2)/(factorial(x-1)*factorial(y-1)) as value from (select x,generate_series(1,8) as y from (select generate_series(1,8) as x) as s) as a group by x,y order by value;
Morgan,
Thank you for offering a solution to this SQL challenge – there are a couple of other SQL challenges on this blog.
Postgres certainly seems to offer features/funtions that make this problem seem easy to solve, based on the solution that you offered.
If I recall correctly, I thought that one of Postgres greatest asset was its ability to nearly behave as a drop-in replacement for Oracle Database. Postgres ability to select rows without specifying a datasource is interesting, as is its function to calculate factorials.