SQL Server Magazine

Editor's Note: Send your experts-only T-SQL tips to Itzik Ben-Gan at blackbelt@sqlmag.com. If we use your tip in the magazine, you'll receive $100 and an exclusive T-SQL Black Belt shirt!

Several recent SQL Server Magazine articles have addressed hierarchical structures in a database environment. In "Maintaining Hierarchies," July 2000, I discussed solutions for managing hierarchical data and showed how to manipulate hierarchical data by adding columns to a table. In "Expanding Hierarchies" (http://www.sqlmag.com, InstantDoc ID 15715), Muhammad Nadeem Akhter showed how to manipulate hierarchical data by using stored procedures and gave you a glimpse of how to use user-defined functions (UDFs) to manipulate hierarchies in SQL Server 2000. In this article, I show you how to use UDFs in hierarchical environments and how powerful UDFs can be for enhancing hierarchical data-manipulation capabilities. (For more information about UDFs, see Robert Vieira, "User-Defined Functions," November 2000.) In my examples, I use an Employees table in which each employee has an attribute called mgrid, which holds the manager ID of the employee. Each manager is also an employee, which creates hierarchical relationships. Listing 1 shows the script that creates and populates the Employees table.

Getting Ancestors
Let's jump right into the first example—retrieving a manager in a requested level. For example, let's say that you want to return the manager who is two levels above a particular employee. You can approach this task in two ways: by using recursion or by using loops. Let's start with the recursive solution. Essentially, recursion means that a routine calls itself. To avoid a situation in which a routine infinitely calls itself, you must always use recursion with a proper termination check. Correctly used, recursion can solve problems that would otherwise be too complex to solve. (The sidebar "Using Recursion to Solve the Hanoi Towers Puzzle," page 26, gives an example of a problem that recursion can solve.) However, in many cases, you can simply use loops instead of recursion. Using loops is often a better choice because recursive calls can consume more resources than loops.

Listing 2 shows the dbo.ufn_GetAncestor function, which uses recursion to return the correct manager. The dbo.ufn_GetAncestor function gets two arguments: @empid is the employee ID, and @lvl is a value that specifies how many levels above an employee the manager's level is. First, the function performs some safety checks to make sure that the supplied arguments are valid. If the arguments aren't valid, the function returns NULL. Next, the function performs the recursion termination check: If the argument supplied as the level is 0, the function simply returns the employee ID, which was also provided as an argument. Last, the function executes the recursive call, which is amazingly simple—the function calls itself and passes as arguments the manager of the specified employee and the level -1. In essence, the function is asking for the ancestor of the manager of the specified employee that is n -1 levels above the manager, where n is the level you supplied. The recursion aborts as soon as the level drops to zero or a manager in a higher level can't be found. In the latter case, the function returns NULL to show that the request can't be fulfilled.

Recursion has two limitations. One limitation is general and applies to recursion in most environments; the other is specific to SQL Server. The general limitation is recursion's significant resource consumption. Each function holds memory structures that contain the function's code and that keep track of the function's variables. As recursion continues, several occurrences of the function are active and this behavior consumes resources.

The SQL Server-specific limitation is SQL Server's design specification that limits the number of supported nesting levels to 32. This specification gives adequate flexibility in performing recursion and eliminates the possibility of infinite recursive calls in poorly written routines—for example, those with no termination checks. Therefore, the above function supports only requests for managers who are within 32 levels above the employee provided as an argument. In an organizational tree, you rarely need to support more than 32 levels. But if you're working with an organizational tree that has more than 32 levels, you have to provide a solution that doesn't involve recursion. In my example, I provide a simple, nonrecursive solution by using a loop. Listing 3 shows the code for the revised function. In each iteration, I retrieve the manager of the employee and decrement the @lvl argument. After the current level drops to zero, the function is complete.

You can now test either function. Both return the same result if you provide the same arguments. For example, to retrieve the manager who is 2 levels above David (whose empid is 11), you would execute the following statement:

SELECT dbo.ufn_GetAncestor(11, 2)

This statement returns the employee ID of Janet, which is 3. If you want to retrieve the full details of the manager who is 2 levels above David, you would issue the following query:

SELECT * FROM Employees WHERE empid =
	dbo.ufn_GetAncestor(11, 2)

To get all the employees and their managers who are two levels above, you can issue the following query:

SELECT E.empname AS employee, A.empname AS ancestor
FROM Employees AS E LEFT OUTER JOIN Employees AS A
  ON A.empid = dbo.ufn_GetAncestor(E.empid, 2)

This query performs a self-join between the Employees table and itself. The join condition ensures that each employee is matched with her manager, who is two levels above. I used a LEFT OUTER JOIN in this query to ensure that all employees—including those who don't have a manager who is two levels above—are included in the result.

   Prev. page   [1] 2     next page