Recursive function using union

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

Transact-SQL (2000)

Recursive function using union

Author

Topic

orange
Starting Member

5 Posts

Posted - 2004-10-09 : 10:17:04

Hello,

I'm building a forum and would like to build a tree out of all messages. Have looked at the different approaches to this problem that has been presented to this forum, but all I actually want to do is to fast fetch all nodes from a tree with a starting point.

I tried to make a recursive function, but I'm stuck. Anyone know how I can dynamically pass the parameters here?


-- Create the table, we use the same values as can be found at
-- http://www.seventhnight.com/treestructs.asp
CREATE TABLE tree (parent_id INT, node_id INT)

INSERT INTO tree (parent_id, node_id) Values (0,1)
INSERT INTO tree (parent_id, node_id) VALUES (0,2)
INSERT INTO tree (parent_id, node_id) VALUES (0,3)
INSERT INTO tree (parent_id, node_id) VALUES (1,4)
INSERT INTO tree (parent_id, node_id) VALUES (1,5)
INSERT INTO tree (parent_id, node_id) VALUES (2,6)
INSERT INTO tree (parent_id, node_id) VALUES (3,6)
INSERT INTO tree (parent_id, node_id) VALUES (3,7)
INSERT INTO tree (parent_id, node_id) VALUES (4,8)
INSERT INTO tree (parent_id, node_id) VALUES (4,9)
INSERT INTO tree (parent_id, node_id) VALUES (6,10)
INSERT INTO tree (parent_id, node_id) VALUES (7,11)
INSERT INTO tree (parent_id, node_id) VALUES (7,12) 

-- The traverse tree function
CREATE FUNCTION fetch_tree_nodes(@parent_id int)
RETURNS @return table (node_id int, parent_id int)
AS
BEGIN
	-- Declarations
	DECLARE @count int

	-- Check how many subnodes there are to the current
	SELECT @count = COUNT(*)
	FROM tree
	WHERE parent_id = @parent_id

	-- End of recursion, when there's no subnodes
	IF @count = 0
	BEGIN
		RETURN
	END

	-- Make the return result
	INSERT INTO @return
	SELECT node_id, parent_id
	FROM tree
	WHERE parent_id = @parent_id
	UNION ALL
  	SELECT node_id, parent_id
	FROM dbo.fetch_tree_nodes(...)

	RETURN
END

-- Fetch the whole tree, start with all nodes which have parent 1
SELECT * FROM dbo.fetch_tree_nodes(1)

Is there a clever way to get the value from the previous query as the function argument? Maybe T-SQL can't pass variables when using UNION? I got that idea when reading this article:
http://www-106.ibm.com/developerworks/db2/library/techarticle/0307steinbach/0307steinbach.html

Thanks in advance!

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-10-09 : 11:52:53

hey let me point you two my almost finished expanded article... I actually handle this question, all though I do not use a recursive function...

http://www.seventhnight.com/treestructs.asp
and
http://www.seventhnight.com/treestructs2.asp
and
http://www.seventhnight.com/treestructs3.asp

EDIT: Just updating the links as they aren't good anymore

Corey

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-10-09 : 11:55:33

by the way....
From BOL:
On @@nestlevel

quote:

Each time a stored procedure calls another stored procedure, the nesting level is incremented. When the maximum of 32 is exceeded, the transaction is terminated.

Thus this would limit your tree to 32 levels...

Corey

orange
Starting Member

5 Posts

Posted - 2004-10-09 : 17:47:36

Thanks for the answer. I looked into your solution earlier, maybe I just didn't really understand it. What striked me is that there ought to be a simpler solution just to present all nodes.

My first solution before I started to do some SQL research was to use local cursors in a recursive manner. Then I bumped into a website that said that cursors was evil. From what I've understood, one shouldn't use cursors at all due to locking. But since I'm only using one directional READONLY cursors, is that really a problem?

Cheers

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-10-09 : 19:08:53

Keep it simple; no need for recursion or cursors:

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=25964

- Jeff

orange
Starting Member

5 Posts

Posted - 2004-10-09 : 20:42:44

Thanks Jeff! That looks just like what I was trying to accomplish. I will try it out later, don't quite understand how it's possible to retrieve all children -- but that's probably just because I'm tired and are going to sleep. :)

Great work! (Just wonder why I missed that in the forum.. :/)

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-10-09 : 23:31:09

The article just describes how to build a set paths from which you can derive all kinds of answers about a tree. If you just want a list of the all of the children, then the building of the paths table is pretty close to what you want...


Declare @nodes table (NodeId int)
Insert Into @nodes Values(1)
Insert Into @nodes Values(2)
Insert Into @nodes Values(3)
Insert Into @nodes Values(4)
Insert Into @nodes Values(5)
Insert Into @nodes Values(6)
Insert Into @nodes Values(7)
Insert Into @nodes Values(8)
Insert Into @nodes Values(9)
Insert Into @nodes Values(10)
Insert Into @nodes Values(11)
Insert Into @nodes Values(12)


Declare @tree table (pNodeId int, cNodeId int, processed bit default(0))
Insert Into @tree (pNodeId, cNodeId) Values (0,1)
Insert Into @tree (pNodeId, cNodeId) Values (0,2)
Insert Into @tree (pNodeId, cNodeId) Values (0,3)
Insert Into @tree (pNodeId, cNodeId) Values (1,4)
Insert Into @tree (pNodeId, cNodeId) Values (1,5)
Insert Into @tree (pNodeId, cNodeId) Values (2,6)
Insert Into @tree (pNodeId, cNodeId) Values (3,6)
Insert Into @tree (pNodeId, cNodeId) Values (3,7)
Insert Into @tree (pNodeId, cNodeId) Values (4,8)
Insert Into @tree (pNodeId, cNodeId) Values (4,9)
Insert Into @tree (pNodeId, cNodeId) Values (6,10)
Insert Into @tree (pNodeId, cNodeId) Values (7,11)
Insert Into @tree (pNodeId, cNodeId) Values (7,12)

--Select * From @Tree

Declare @lastCnt int,
	@startNode int

Set @StartNode = 3

Declare @children table (startNodeId int, pNodeId int, cNodeId int)

Insert Into @children
Select Distinct
	StartNodeId = @startNode,
	pNodeId,
	cNodeId
From @Tree where pNodeId=@startNode

Select @lastCnt = @@RowCount

While @lastCnt > 0
Begin
	Insert Into @children
	Select Distinct
		Z.StartNodeId,
		Z.pNodeId,
		Z.cNodeId
	From
		(
		Select 
			StartNodeId = @startNode,
			B.pNodeId,
			B.cNodeId
		From @children A
		Inner Join @Tree B
		On A.cNodeId = B.pNodeId
		) Z
	Left Join @children Y
	On Z.pNodeId = Y.pNodeId
	and Z.cNodeId = Y.cNodeId
	Where Y.pNodeId is null
	
	Select @lastCnt = @@RowCount
End

Select * From @children

Corey

dev@
Starting Member

1 Post

Posted - 2004-10-27 : 17:11:57

http://www.codeproject.com/cs/database/Trees_in_SQL_databases.asp

DustinMichaels
Constraint Violating Yak Guru

464 Posts

Posted - 2004-10-27 : 17:20:56

http://www.sqlteam.com/item.asp?ItemID=8866

I've used the info from this link a couple of times to store hierarchical (sp?) data.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources