Recursive UDF

Question

Recursive UDF

Tim OPry

SSCrazy

Points: 2988
More actions
November 27, 2007 at 1:09 pm

#62199

I have a very simple table:
if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[ClientReferrals]') and OBJECTPROPERTY(id, N'IsUserTable') = 1)
drop table [dbo].[ClientReferrals]
GO
CREATE TABLE [dbo].[ClientReferrals] (
[ReferralID] [int] IDENTITY (1, 1) NOT NULL ,
[ClientID] [uniqueidentifier] NOT NULL ,
[ClientReferredID] [uniqueidentifier] NOT NULL
) ON [PRIMARY]
GO
Which contains GUIDs for client records - basically, who referred whom.
What I am trying to create is a UDF that returns a list of Clients of both the 'downstream' and 'upstream', so I can limit the selection of clients to prevent recursion.
By 'downstream', I mean all clients referred by a ClientID and all of their subsequent children/referrals. 'Upstream' would be the converse - since a client cannot also refer someone that is either in the parent or child (up/down) link of their chain.
Currently, I have a recursive UDF to create the downstream that uses a cursor -which, I can 'reverse' to create the upstream, but would like to get rid of cursors and have one UDF to return both directions.
Any suggestions?

Viewing 5 posts - 1 through 4 (of 4 total)

You must be logged in to reply to this topic. Login to reply

Jeff Moden SSC Guru Points: 1004340 More actions · Answer 1

Any suggestions?

Yes... why recalculate the same thing over and over and over? How often does the "tree" change? You need to convert your "Adjacency" model to a "Nested Set" model... or at least develop a "sister" table with the "Nested Set" model in it. See the following URLs...

http://www.sqlteam.com/article/more-trees-hierarchies-in-sql

http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=1266295

If you have a limited number of levels, say, 800 or less, you might be able to get away with a "cheap shot" at hierarchies using something like the following... I haven't figured out how to write the "Upline" code for it, but it shouldn't be too difficult...

--=======================================================================================

-- Setup some test data... note that nothing in this section is part of the actual

-- solution.

--=======================================================================================

--===== Setup a "quiet" environment

SET NOCOUNT ON

--===== Create a table to hold some test data.

-- This is NOT part of the solution

CREATE TABLE #yourtable

(

ID INT,

ParentID INT,

Descrip VARCHAR(20)

)

--===== Populate the test table with 2 "trees" of data

INSERT INTO #yourtable

(ID,ParentID,Descrip)

SELECT 9,NULL,'County 1' UNION ALL --Note NULL, this is top node of "Tree 1"

SELECT 2,9 ,'C1 Region 1' UNION ALL

SELECT 4,9 ,'C1 Region 2' UNION ALL

SELECT 3,2 ,'C1 R1 Unit 1' UNION ALL

SELECT 5,2 ,'C1 R1 Unit 2' UNION ALL

SELECT 6,4 ,'C1 R2 Unit 1' UNION ALL

SELECT 7,NULL,'County 2' UNION ALL --Note NULL, this is top node of "Tree 2"

SELECT 8,7 ,'C2 Region 1' UNION ALL

SELECT 1,9 ,'C1 Region 3'

--=======================================================================================

-- The following code makes a Hierarchy "sister" table with strings that are used

-- to traverse various hierarchies.

--=======================================================================================

--===== Create and seed the "Hierarchy" table on the fly

SELECT ID,

ParentID,

Descrip,

Level = 0, --Top Level

HierarchyString = CAST(STR(ID,5) AS VARCHAR(8000))+' '

INTO #Hierarchy

FROM #yourtable

WHERE ParentID IS NULL

--===== Declare a local variable to keep track of the current level

DECLARE @Level INT

SET @Level = 0

--===== Create the hierarchy in the HierarchyString

WHILE @@ROWCOUNT > 0

BEGIN

SET @Level = @Level + 1

INSERT INTO #Hierarchy

(ID, ParentID, Descrip, Level, HierarchyString)

SELECT y.ID,y.ParentID,y.Descrip, @Level, h.HierarchyString + STR(y.ID,5) + ' '

FROM #yourtable y

INNER JOIN #Hierarchy h

ON y.ParentID = h.ID --Looks for parents only

AND h.Level = @Level - 1 --Looks for parents only

END

--=======================================================================================

-- Now, demo the use of the sister table

--=======================================================================================

--===== Display the entire tree with indented descriptions according to the Level

SELECT ID,

ParentID,

Level,

LEFT(REPLICATE(' ',Level*2)+descrip,30),

HierarchyString

FROM #Hierarchy

ORDER BY HierarchyString

--===== Select only the "downline" for ID 2 including ID 2

SELECT ID,

ParentID,

Level,

LEFT(REPLICATE(' ',Level*2)+descrip,30),

HierarchyString

FROM #Hierarchy

WHERE HierarchyString LIKE '% 2 %'

ORDER BY HierarchyString

drop table #Hierarchy

drop table #yourtable

The key is, no matter what method you use, figure out the whole tree so you don't have to keep recalculating parts of the tree...

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Tim OPry SSCrazy Points: 2988 More actions · Answer 2

Thank you for the input (and two links) - both very helpful. I recall reading Celko's article a while back, but like the other author find that method a bit much, especially for my usage, which is a simpler heirarchial issue.

The BOL sproc works better than my recursive UDF, so at a minimum I will try to adapt it to calc the upstream.

Matt Miller (4) SSC Guru Points: 124210 More actions · Answer 3

Tim OPry (11/27/2007)
.
By 'downstream', I mean all clients referred by a ClientID and all of their subsequent children/referrals. 'Upstream' would be the converse - since a client cannot also refer someone that is either in the parent or child (up/down) link of their chain.

I wasn't entirely clear about whether 'cannot' meant you were going to code to not allow that, or if it's one of those "it's never going to happen so we don't need to code for it". I'd venture to say it's going to happen, so prevent it somehow. You could very easily blow out you DB if you don't specifically code to prevent expanding circular references (exponentially as a matter of fact).

----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?

Tim OPry SSCrazy Points: 2988 More actions · Answer 4

The intent is to prevent it - otherwise, it would cause a recursive loop and prevents our reports from running. That is also why I must include the 'upstream'.