CTE, Recursion and Math

Tags: ,
Comments: No Comments
Published on: May 23, 2011

Earlier this month we had a TSQL Tuesday on the topic of CTEs.  I bailed on my submission because I already posted some CTE examples and was bone dry on what I could write about.

Later I saw a request for some help on creating combinations and permutations from TSQL.  I thought about this request and finally came up with the idea to use CTEs to do it.  The idea came about based on seeing multiple suggestions in that thread and then combining some of the pieces together.  Though not a suggestion, per-se, but seeing in the code submitted that a factorial was being used along with the sum of all integers from 1 to the given integer (or summation), I decided I would incorporate that into my solution.

I thus set out to create a solution that would use a CTE to generate those permutations, the summation, and the factorial.  In this article I will just be focusing on how I came to produce the factorial and summation using a little bit of Recursive CTE.  Also, we will see an alternative solution to calculating the summation.  For help in setting up the structure of a recursive CTE, you may want to refer to this article.

Here is the script first, and then I will explain later.

[codesyntax lang="tsql"]

[/codesyntax]

As you can see, I am using several CTEs in this script.  The first group of CTEs is to create a Dynamic Tally (Numbers) table.  The last two CTEs are performing the same thing but with a bit of filtering applied.  When you look at them, you should note that the first one is Casting the Factorial to a Numeric data type.  The last CTE is casting the Factorial to a FLOAT data type.  This isn’t necessarily required but more of an aesthetic for myself.  So any number greater than 33 will use the FLOAT data type and anything less than 34 will use the numeric data type.

The FLOAT data type will support those smaller numbers – that’s not an issue.  The Numeric data type will not support the larger values (it is limited to 38 characters).  We start running into arithmetic overflow at 34! and must use the FLOAT at that point.  The problem is that I prefer to avoid the overflow style of displaying the numbers except when necessary.  For simplicity sake, you could eliminate the filtering between the CTEs and simply use the FLOAT across the board.

Since I am trying to filter between the two and create a single row result set, I also have a second issue that is created by this code.  That issue is resolved and seen when performing the final select from the CTEs.  If the query requires the use of FLOAT, I will get an error message with an arithmetic overflow again unless I Convert the Numeric and Float results into something that is compatible between the two.  I chose to use VarChar(100) in this case.

Note, also, that I am using a FULL OUTER Join in the final query.  This is due to the fact that I will see results in either the CTEMathN or CTEMathF CTE but not both.

Now down into the nitty gritty.  Let’s look at CTEMathN to see how we are getting the factorial and the summation.

[codesyntax lang="tsql"]

[/codesyntax]

First we have the required anchor definition.  Second we have the recursion definition joined by the Union All and referencing the same CTE where both of these pieces reside.

The factorial is easy enough.  Since a Factorial is n! or n(n-1) we can multiply n by the previous n in the sequence.  We can get both of those values through our join statement where we join back out to the Tally CTE and showing an increment in the number (here I am join CTETally.n to CTEMathN +1).  This ensures we will move through the record set (or recurse).

The same principle applies for the summation.  We add each number in the sequence from 1 to n to retrieve our result.  So, much the same as the factorial, I add n to the previous value of n and proceed from there through the record set.

Note also that I threw an additional limiting factor on the where clause.  I want to make sure that I do not try to recurse through a record set that includes numbers outside of my range.

Now, since I only really care about the factorial and summation for the number I inserted in the variable at the beginning, I want to make sure that I have a filter added to the final select clause.  Here is that final filter…

[codesyntax lang="tsql"]

[/codesyntax]

This enforces a single record will be returned by selecting only the last iteration.  Iteration is another column in the CTEs that is used during our recursion process.  The iteration column just increments by a value of one with each pass.

Pretty easy eh?

Now, if all you need is a summation and it is not used to control result sets (like mine will be in the next bit where we discuss permutations), then you could rip out the aggregation stuff and just use this in the final select statement…

[codesyntax lang="tsql"]

[/codesyntax]

That would be in place of this bit…

[codesyntax lang="tsql"]

[/codesyntax]

Have fun with it!!

No Comments - Leave a comment

Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">






Calendar
May 2011
M T W T F S S
« Apr   Jun »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  
Content
SQLHelp

SQLHelp


Welcome , today is Thursday, July 24, 2014