CTEs with Multiple Recursive Members, Part 2

Downloads
144833.zip

When people write recursive common table expressions (CTEs) in T-SQL, they mostly use a single recursive member (the inner query with the reference to the CTE name). In Part 1 of this article ("CTEs with Multiple Recursive Members"), I covered more complex types of recursive CTEs that involve multiple recursive members. I demonstrated two practical use cases involving genealogy queries and the nested sets model for graphs. In this article, I demonstrate a third use case that isn't practical -- but I had a lot of fun working on it! I explain how to use a recursive CTE with multiple recursive members to draw a Koch snowflake. First, I describe what a Koch snowflake is. Next, I provide solutions to generate a Koch snowflake with T-SQL. For more information about Koch snowflakes, see the Wikipedia "Koch snowflake" entry.

Koch Snowflake

A Koch snowflake is a certain kind of fractal. You start with an equilateral triangle, as Figure 1 shows.

Figure 1: Starting Step for Koch Snowflake

To generate the next step of the fractal, you apply the following for each line segment from the previous step:

1. Draw a line made of one third of the line from the previous step (call the length L/3).
2. Turn 60 degrees outward and draw a line with a length L/3.
3. Turn 120 degrees inward and draw a line with a length L/3.
4. Turn 60 degrees outward and draw a line with a length L/3.

Figure 2 shows the transition of a line segment from one step to the next.

Figure 2: Transition to Next Step 

You can apply this logic recursively for any number of iterations to generate a Koch snowflake with varying levels of detail. As an example, Figure 3 demonstrates the fractals generated in each of five iterations of this recursive algorithm.

Figure 3: Koch Snowflake Iterations 

Next, I'll demonstrate how you can generate a Koch snowflake with T-SQL using a recursive CTE.

Koch Snowflake Table Function

In this section, I'll show you how to draw a Koch snowflake using a recursive CTE and the GEOMETRY spatial datatype. The solution relies on a helper inline table-valued function called GetEndPoint. The function accepts as inputs the x and y coordinates of a starting point of a line, an angle (in degrees) and distance, and it returns the x and y coordinates of the end point of the line. Run the code in Listing 1 to create the function in a database of your choice.

The function uses the following expressions to compute the end point's x and y coordinates:

Since the COS and SIN functions in T-SQL accept the angle in radians, the code converts the input angle in degrees to radians using the expression PI()*@angle/180.

I implemented a solution that draws a Koch snowflake using an inline table function called KochSnowflakeColored. Run the code in Listing 2 to create the function. This function accepts as input the number of iterations that you want the function to apply. It returns the snowflake generated by the last iteration as a set of GEOMETRY typed values representing the line segments of the snowflake.

The CTE body defines three anchor members, generating the three sides of the triangle representing the first step, or iteration, of the snowflake. As an example, the following anchor member implements side b of the triangle (see Figure 1):

I chose an arbitrary length of 100 for the lines in the first iteration and an arbitrary starting point with coordinates x = 0 and y = 0. SQL Server Management Studio (SSMS) will adapt to the coordinates and proportions of the snowflake when presenting it in the Spatial results tab. So this query returns the following information for side b of the triangle: Length = 100; starting point (x, y) = (0, 0); angle = 60 degrees (with respect to x axis, anticlockwise). The line end point's coordinates are computed by the GetEndPoint function. In a similar way, two additional anchor members generate the information for sides a and c of the triangle.