Home > Programming > Creating Recursive SQL Calls for Tables with Parent-Child Relationships

Creating Recursive SQL Calls for Tables with Parent-Child Relationships

recursI ran into an interesting problem today while considering how to find out where subordinate employees fit into an organizational chart. The problem was that I need to list every employee that was “under” a given employee, but could only really do this in SQL – if I were to try and do this from within PHP, it would have made a single exception case where we build an SQL query based on another query – something I’d rather not have to do. Let’s see if this little graph can more adequately describe what the issue was:

 +-----------+-------------+
| Employee  | Subordinate |
| --------- | ----------- |
| Frank     | Tim         |
| Frank     | Jacob       |
| Frank     | John        |
| Frank     | Mark        |
| Tim       | Chris       |
| Tim       | Randy       |
| Randy     | Dave        |
| Mark      | Joey        |
+-----------+-------------+

So, with this list, the goal was that if I were looking for all subordinate employees under Frank, it would return rows with the names “Tim, Jacob, John, Mark, Chris, Randy, Joey”, since everyone else is under Frank. However, if I were to look for Tim’s subordinates, I’d only get “Chris, Randy, Dave”, and if I looked for Joey, I wouldn’t get any rows.

What does this mean, then? It means we have to search the table multiple times – once for each node, or employee, that we find – the first entry we give it as well as every entry below that employee. It also means we need to hard code the number of levels of employees we’re looking for, or, gasp, use recursion in our SQL.

To fix this issue, I started by digging around in Google. I’m using MSSQL, so maybe I could have created a stored procedure, but I tend to shy away from them in case I ever want to change database technologies. What I found was a really great PDF that almost matched my needs over at NaSPA . The problem with the query he came up with, however, is that it merely wanted to know the number of subordinates, where we’re interested in much more data than that.

This is the solution I came up with based on Rob Mala’s code:

WITH temp_orgChart (Employee, Subordinate, iteration) AS

(

SELECT Employee, Subordinate, 0

FROM orgChart WHERE Employee = ‘Frank’

UNION ALLSELECT a.Employee, b.Subordinate, a.iteration + 1

FROM temp_orgChart AS a, orgChart AS b

WHERE a.Subordinate = b.Employee

)

SELECT Subordinate

FROM temp_orgOrgchart

Let’s take a look at this step by step then, shall we? Maybe you’ll get a grasp of how to adapt this for your needs.

WITH temp_orgChart (Employee, Subordinate, iteration) AS

(

All this says is that we’re creating a temporary table to do our SELECT command on, and that this table is going to have three columns – “Employee”, “Subordinate”, and “iteration”.

SELECT Employee, Subordinate, 0

FROM orgChart WHERE Employee = ‘Frank’

UNION ALL

Here, we’re doing our first step in the recursive technique – finding the very first employee to start with. Notice that we’ve added a “0? to the end of the SELECT list – this is our index. As we increase our index, we go deeper into the tree of employees. Also, if we wanted to start with a different employee, we’d name him here instead of Frank.

We also did a UNION ALL afterwards. This means we’re going to include everything in the next statement too.

SELECT a.Employee, b.Subordinate, a.iteration + 1

FROM temp_orgChart AS a, orgChart AS b

WHERE a.Subordinate = b.Employee

This is our recursive step. This means it’s essentially the equivalent of calling a specific SELECT statement with different input over and over again based upon the results of the preceding SELECT statement. Here, we’re grabbing the current employee that we just found, and looking for their subordinate in the organizational chart. When we find one, we look for that subordinate’s subordinates and if we find one we do it again until we don’t find any more. We then go back to the previous subordinate and keep digging.

The process goes like this:

  1. The original step (before recursion) adds the following values to the temporary table:

    Frank, Tim, 0

    Frank, Jacob, 0

    Frank, John, 0

    Frank, Mark, 0

  2. The first recursive step looks into the existing temporary table, and sees that Tim has people below him, and adds the following values to the temporary table:

    Tim, Chris, 1

    Tim, Randy, 1

  3. The recursion then sees that Randy has someone below him:

    Randy, Dave, 2
  4. The recursion doesn’t see anyone else below, so it returns to the last level and adds:

    Mark, Joey, 1

This is the confusing step, and may be difficult to wrap your mind around. Hell, it was a mess for me to figure out and I’m not entirely sure the above process is exactly the way it’s done, but I do know that the code works. It’s okay – take the code, and play with it. Keep in mind that every iteration is a new “level” on the chart.

)

SELECT Subordinate

FROM temp_orgOrgchart

Back to the simple stuff – this just says that the data we want is in the column “Subordinate” in the temporary table we’ve just filled up.

This recursive SQL statement really isn’t too difficult, as there’s only one really confusing bit to it – the actual recursion.

I hope this helps a few of you put together the calls you need and saves you some time.

Categories: Programming Tags: ,
  1. No comments yet.
  1. No trackbacks yet.
You must be logged in to post a comment.