Recursion is a well known technique in computer science. It can also be applied using T-SQL in SQL Server but there is a restriction which is that the nesting calls/levels is limited to the depth of 32 only. Even though, recursive SQL is a very useful technique. You can even implement a factorial recursive algorithm using it as I reference below. First let’s illustrate simple example of a parent/child table and then apply the recursion on it.
Egypt Population Sample
Let’s assume we have a structure representing the population in Egypt as the root and all its cities & districts in the following form:
Let’s represent this structure in a parent/child table (EgyptPopulation Table):
Now the case is that we want to update all roots of a certain leaf after the leaf value is changed as the following:
- We set the population of Mohandessin to 6 (instead of 4)
- Since mohandessin is a child of Cairo & Cairo is a child of Egypt(the root) then both will be affected
- Cario = Heliopolis + Maadi + Mohandessin = 5 + 3 + 6 = 14
- Egypt = Cairo + Alex = 14 + 7 = 21
Recursion will be a very useful technique to apply this. T-SQL recursion is similar to the regular recursion we use in programming. As we declare a method and call it in its own body putting in consideration a stopping condition in order not to enter an infinite loop, we will do the same in T-SQL recursion using stored procedures. Here is the implementation of the recursive stored procedure:
--This is only to drop the procedure if it was created before
IF EXISTS (SELECT * FROM sysobjects
WHERE id = object_id('UpdateEgyptPopulation')
and OBJECTPROPERTY(id, 'IsProcedure') = 1)
DROP PROCEDURE UpdateEgyptPopulation
GO
CREATE PROCEDURE UpdateEgyptPopulation
@childID INT --The ID of the updated child which value was changed (ex: Mohandessin)
AS
SET NOCOUNT ON
DECLARE @parentID INT --A variable to hold the ID of the parent of the current child in the loop
BEGIN
SELECT @parentID = ParentID FROM EgyptPopulation WHERE ID=@childID
IF (@parentID != -1) --Condition to test whether the root is reached or not
BEGIN
--Update the parent of the current child in the loop
UPDATE EgyptPopulation SET Goal = (SELECT SUM(Goal) FROM
EgyptPopulation WHERE ParentID = @parentID)
WHERE ID = @parentID
--Recurse to update all the parents to the root level passing the current parent ID
EXEC UpdateEgyptPopulation @parentID
END
ELSE
BEGIN
RETURN --If the root node is reached (no more parents) end the recursion
END
END
GO
The logic in this sotred procedure is as follows:
- Passing the ID of the updated child in to the stored procedure
- Declaring a variable @parentID and querying the ID of the parent using the child’s ID
- If the ID of the parent is null (-1) then we stop the recursion
- If not, then we update the parent population by getting the sum of all its childs
- Then we call the same procedure by passing the ID of the parent itself to update it parent & so on until we reach the root (Egypt) which has no parents. In this condition the loop will be broken
Bare in mind that the number of nesting calls in limited to 32 only. This means that this technique cannot be applied on a parent/child structure with depth more than 32.
References
Recursion in T–SQL
http://msdn2.microsoft.com/en-us/library/Aa175801(SQL.80).aspx
Using recursion in stored procedures (Factorial example)
http://articles.techrepublic.com.com/5100-9592_11-5700193.html
