SQL Server Magazine

Recursion is the property or quality of self-reference. In programming terms, recursion refers to a routine that repeatedly calls itself until a certain condition is fulfilled. One powerful way that SQL Server database developers can use recursion is to traverse hierarchies—collections of items that have parent-child relationships. People deal with hierarchies all the time: Every day, you have a series of tasks you must prioritize and then perform. Also, most people work within a hierarchy of employees. The classic way to represent a hierarchy within a database is to add a parent key to the object. A parent key is simply the primary key of an object that has a parent relationship to the current object. To see an example, let's define a management structure. Table 1 defines a typical employee, Chris; the record for Chris's boss appears in Table 2. Note that the boss's record has an ISupervisorID of 0 and that Chris's record has an ISupervisorID of 212, the IEmployeeID value in the boss's record. These values specify that the boss record is a parent of Chris's record. The matching values of ISupervisorID in Chris's record and IEmployeeID in the boss's record form a data link—or parent key—between the two records.

Now, as a simple example of stored-procedure recursion in a hierarchy, let's say that you're tasked with generating a list of all employees and their subordinates. You need to write a script to retrieve all the records at the top level (i.e., the employees whose ISupervisorIDs are 0), then grab the child records for each record in that set, and so on in a recursive process. Listing 1 contains pseudocode for such a process, and Table 3 is an example of output that meets your needs.

This approach is logically sound, but when you turn the pseudocode into the SQL code in Listing 2 and run it, you get the execution error that Figure 1 shows. The code worked for a level, then failed because SQL Server declared the cursor named cur_Level with a connection-level scope. This means that during its lifetime, the cursor can be accessed across every query that occurs on the same connection. Because the recursive calls occur on this connection, they inherit the cursor, causing an error whenever there's an attempt to create another cursor with the same name. You have two ways of fixing this problem.

First, you could change the Default to local cursor database option setting (support for local cursors is a feature of SQL Server 7.0). By default, this option is set to GLOBAL to conform to the requirements of earlier SQL Server releases, but you can set the option to LOCAL to bypass this problem if you think you'll be using locally scoped cursors often.

A second option for getting rid of the error is to simply add the LOCAL keyword to the declaration, as in Listing 3. After you add the LOCAL keyword, the code performs perfectly, giving you the results that Figure 2 shows.

Now let's look at a more common and useful example: a threaded discussion list. Recursion is a good tool to use in creating a discussion list because messages are presented in a parent-child format, with base-level messages first, followed by replies to that base-level message.

A threaded discussion list is a typical hierarchy: Messages are either top-level subjects or responses (children) to other messages. The message structure looks like Table 4. Let's say that this message board becomes enormously popular, receiving thousands of hits per second. An effective scaling strategy for a high-use application is forward caching, which means that you pregenerate the content to display later. Inserting the content into a cache table ahead of time conserves the server resources that the board's high-traffic conditions demand. Because performance is so important, forward caching is a better option than simply selecting the content through stored procedures.

When you use ADO to access the output of these procedures, the results are represented as a series of recordsets that are accessible through ADO's NextRecordset method (for more information about NextRecordset, see MSDN online documentation). The process of generating messages for users of the discussion list comprises two steps. First, when the user selects the main page, SQL Server generates the message board from a forward cache table called tblForumCache. Then, when the user creates a new message or responds to one, SQL Server uses the recursive stored procedure to regenerate the cache table.

Besides simply displaying the message, you'll want to display how many replies a particular message has, as well as the date and time that each message was created. The final output should look something like Table 5.

   Prev. page   [1] 2     next page