counting number of left and right nodes for parent

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

SQL Server Development (2000)

counting number of left and right nodes for parent

Author

Topic

afroz
Starting Member

6 Posts

Posted - 2010-09-14 : 08:36:45

Hi!
I'm using sql server 2000, I need to count number of nodes in left and right side of a root node....
suppose i've entries in table as

node parent_node Position node_name
1 0 'L' abc
2 1 'L' b1
3 1 'R' b2
4 2 'L' c1
5 2 'R' c2
6 3 'L' d1

if i supplied node '1' then it should Give result as
left count=3 and
right count =2

actually what i want is this..

For my entries tree will be like this..
1(abc)
/ / (b1) 2 3(b2)
/\ / / \ / (c1)4 5(c2)6(d1)

Now if i give i/p as 1 then
eft count=3 (b1,c1,c2) and
right count =2 (b2,d1)

if the tree is like this...
1(abc)
/ | / | (b1) 2 | 3(b2)
/\ | /
/ \ | /
(c1)4 5(c2)| 6(d1)
| / \
| / | (d2)7 8(e1)

the middle line is just imaginary to differentiate left and right nodes for node '1(abc)'

Now if i give i/p as 1 then
left count=3 (b1,c1,c2) and
right count =4(b2,d1,d2,e1)

I DONT WANT TO USE CURSORS BECAUSE I'VE SOLUTION WITH CURSOR BUT THERE ARE THOUSANDS OF RECORDS IN THE TABLE ,SO EXECUTION TIME OF PROCEDURE IS V VERY HIGH SOMETIMES IT STRUCK SO PLEASE SUGGEST ME SOMETHING......

Please....Please help me out i'm strucked from many days...Thanx in advance..

afrozz..

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2010-09-14 : 10:09:54

can you upgrade to 2005? If you could then this would be a pretty easy recursive CTE.

Here's a method involving a recursive while loop that *should* work on sql 2000


/*
node parent_node Position node_name
1 0 'L' abc
2 1 'L' b1
3 1 'R' b2
4 2 'L' c1
5 2 'R' c2
6 3 'L' d1

if i supplied node '1' then it should Give result as
left count=3 and
right count =2
*/

DECLARE @foo TABLE (
	[node] INT
	, [parent_node] INT
	, [position] CHAR(1)
	, [node_name] VARCHAR(255)
	)

INSERT @foo ([node], [parent_node], [position], [node_name])
      SELECT 1, 0, 'L', 'abc'
UNION SELECT 2, 1, 'L', 'b1'
UNION SELECT 3, 1, 'R', 'b2'
UNION SELECT 4, 2, 'L', 'c1'
UNION SELECT 5, 2, 'R', 'c2'
UNION SELECT 6, 3, 'L', 'd1'

DECLARE @targetNodeID INT SET @targetNodeID = 1
DECLARE @level INT SET @level = 1
DECLARE @rows INT SET @rows = 0

DECLARE @recursiveMap TABLE (
	[nodeID] INT
	, [level] INT
	, [position] CHAR(1)
	)

INSERT @recursiveMap ([nodeID], [level], [position])
SELECT
	[node], 0, [position]
FROM
	@foo
WHERE
	[parent_node] = @targetNodeID

SET @rows = @@ROWCOUNT

WHILE ( @rows > 0 ) BEGIN

	INSERT @recursiveMap ([nodeID], [level], [position])
	SELECT
		f.[node]
		, @level
		, f.[position]
	FROM
		@foo AS f
		JOIN @recursiveMap AS rm ON rm.[nodeID] = f.[parent_node]
	WHERE
		rm.[level] = @level - 1

	SET @rows = @@ROWCOUNT
	SET @level = @level + 1
END

-- Raw dump of recusivemap

SELECT
	@targetNodeID AS [target Node Id]
	, SUM(CASE WHEN [position] = 'L' THEN 1 ELSE 0 END) AS [Left Count]
	, SUM(CASE WHEN [position] = 'R' THEN 1 ELSE 0 END) AS [Right Count]
FROM
	@recursiveMap

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2010-09-14 : 10:10:54

of course -- with the real tables you'd be able to make / use indexes as appropriate for the recursive while loop
should be a lot quicker than a cursor!

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

afroz
Starting Member

6 Posts

Posted - 2010-09-15 : 08:25:32

Thanx Charlie,thank u very much for your valuable reply..
The above code just counts no of nodes which are left and right to parent
But my actual problem is this..
node parent_node Position node_name
1 0 'L' abc
2 1 'L' b1
3 1 'R' b2
4 2 'L' c1
5 2 'R' c2
6 3 'L' d1

if i supplied node '1' then it should Give result as
left count=3 and
right count =2

actually what i want is this..

For my entries tree will be like this..
1(abc)
/ | / | (b1)2 | 3(b2)
/ \ | /
(c1)4(c2)5 | 6(d1)

Now if i give i/p as 1 then
eft count=3 (b1,c1,c2) and
right count =2 (b2,d1)

if the tree is like this...
1(abc)
/ | / | (b1)2 | 3(b2)
/ \ | /
/ \ | /
(c1)4 5(c2)| 6(d1)
| / | / (d2)7 8(e1)

the middle line is just imaginary to differentiate left and right nodes for node '1(abc)'

table entries for above tree is like this

node parent_node Position node_name
1 0 'L' abc
2 1 'L' b1
3 1 'R' b2
4 2 'L' c1
5 2 'R' c2
6 3 'L' d1
7 6 'L' d2
8 6 'R' d2

Now if i give i/p as 1 then
left count=3 (b1,c1,c2) and
right count =4(b2,d1,d2,e1)

plz help me out...awaiting for your valuable reply...

afrozz..

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2010-09-15 : 09:23:17

You could try this, its a bit of a hack though.


DECLARE @foo TABLE (
	[node] INT
	, [parent_node] INT
	, [position] CHAR(1)
	, [node_name] VARCHAR(255)
	)

INSERT @foo ([node], [parent_node], [position], [node_name])
      SELECT 1, 0, 'L', 'abc'
UNION SELECT 2, 1, 'L', 'b1'
UNION SELECT 3, 1, 'R', 'b2'
UNION SELECT 4, 2, 'L', 'c1'
UNION SELECT 5, 2, 'R', 'c2'
UNION SELECT 6, 3, 'L', 'd1'

DECLARE @targetNodeID INT SET @targetNodeID = 1
DECLARE @level INT SET @level = 1
DECLARE @rows INT SET @rows = 0

DECLARE @recursiveMap TABLE (
	[nodeID] INT
	, [level] INT
	, [position] CHAR(1)
	, [node_name] VARCHAR(255)
	)

INSERT @recursiveMap ([nodeID], [level], [position], [node_name])
SELECT
	[node], 0, [position], [node_name]
FROM
	@foo
WHERE
	[parent_node] = @targetNodeID

SET @rows = @@ROWCOUNT

WHILE ( @rows > 0 ) BEGIN

	INSERT @recursiveMap ([nodeID], [level], [position], [node_name])
	SELECT
		f.[node]
		, @level
		, f.[position]
		, f.[node_name]
	FROM
		@foo AS f
		JOIN @recursiveMap AS rm ON rm.[nodeID] = f.[parent_node]
	WHERE
		rm.[level] = @level - 1

	SET @rows = @@ROWCOUNT
	SET @level = @level + 1
END

DECLARE @leftCount INT                 SET @leftCount = 0
DECLARE @rightCount INT                SET @rightCount = 0
DECLARE @leftNodes VARCHAR(8000)       SET @leftNodes = ''
DECLARE @rightNodes VARCHAR(8000)      SET @rightNodes = ''

SELECT
	@leftCount = @leftCount + CASE [position] WHEN 'L' THEN 1 ELSE 0 END
	, @rightCount = @rightCount + CASE [position] WHEN 'R' THEN 1 ELSE 0 END

	, @leftNodes = @leftNodes + CASE [position]
		WHEN 'L' THEN CASE
			WHEN @leftNodes = '' THEN ''
			ELSE ', '
			END
			+ [node_name]
		ELSE ''
		END

	, @rightNodes = @rightNodes + CASE [position]
		WHEN 'R' THEN CASE
			WHEN @rightNodes = '' THEN ''
			ELSE ', '
			END
			 + [node_name]
		ELSE ''
		END
FROM
	@recursiveMap

SELECT
	@leftCount AS [Left Count]
	, @rightCount AS [Right count]
	, @leftNodes AS [Left Nodes]
	, @rightNodes AS [Right Nodes]

The leftNodes and RightNodes variables will probably depend on CLUSTERED INDEX settings in the recursiveMap table you implement.

As I said -- this is a hack. Can you upgrade to 2005?

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

afroz
Starting Member

6 Posts

Posted - 2010-09-16 : 05:54:36

Hi Charlie!

Its just counting the no of nodes which are left positioned and right positioned in tree ,But my requirement quite different..

As i mentioned in the above tree(Second tree with 8 nodes), the table entries are like this

node parent_node Position node_name
1 0 'L' abc
2 1 'L' b1
3 1 'R' b2
4 2 'L' c1
5 2 'R' c2
6 3 'L' d1
7 6 'L' d2
8 6 'R' e1

Now if i give i/p as 1 then
left count=3 (b1,c1,c2) and
right count =4(b2,d1,d2,e1)

But the above query producing the output as

left count=4 (b1, c1, d1, d2) and
right count =3(b2, c2, E1)
This counting based on node position towards parent eg.(b1, c1, d1, d2) are all left positioned in tree and (b2, c2, E1) are all right positioned in tree

i need the left and right counts without node names in paranthesis..

Please note node b1,c1,c2 are in left to parent 'abc' and node b2,d1,d2,e1 are in right to 'abc'...PLEASE PUT A TREE STRUCTURE TO BETTER UNDERSTAND MY PROBLEM, PLEASE CHARLIE..

awaiting for your help.. Thanx in advance..

afrozz..

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2010-09-16 : 06:26:07

AH -- I understand now. You want a count of any record left and right of the orrignal root node!

Here. I've rewritten using temp tables so to add an index.


/*
node parent_node Position node_name
1 0 'L' abc
2 1 'L' b1
3 1 'R' b2
4 2 'L' c1
5 2 'R' c2
6 3 'L' d1
7 6 'L' d2
8 6 'R' e1

MAP
         ---------1--------- 
         |                 |
         2                 3
        / \               / 
       /   \             /   
      4     5           6
                       /                       7   8

*/
IF OBJECT_ID('tempDb..#nodeMap') IS NOT NULL DROP TABLE #nodeMap
CREATE TABLE #nodeMap (
	[node] INT PRIMARY KEY CLUSTERED
	, [parent_node] INT
	, [Position] CHAR(1)
	, [node_name] VARCHAR(50)
	)

CREATE INDEX RECURS_IX_NODEMAP_PARENT_NODE ON #nodeMap ([parent_node])

INSERT #nodeMap
      SELECT 1, 0, 'L', 'abc'
UNION SELECT 2, 1, 'L', 'b1'
UNION SELECT 3, 1, 'R', 'b2'
UNION SELECT 4, 2, 'L', 'c1'
UNION SELECT 5, 2, 'R', 'c2'
UNION SELECT 6, 3, 'L', 'd1'
UNION SELECT 7, 6, 'L', 'd2'
UNION SELECT 8, 6, 'R', 'e1'


IF OBJECT_ID('tempDb..#recurseMap') IS NOT NULL DROP TABLE #recurseMap
CREATE TABLE #recurseMap (
	[node] INT PRIMARY KEY
	, [treeDirection] CHAR(1)
	, [level] INT
	)

DECLARE @startNode INT                 SET @startNode = 1
DECLARE @level INT                     SET @level = 1
DECLARE @rows INT                      SET @rows = 0

-- Initial Insert
INSERT #recurseMap
SELECT
	[node], [position], @level
FROM
	#nodeMap
WHERE
	[parent_node] = @startNode

-- Recursive Loop
SET @rows = @@ROWCOUNT
SET @level = @level + 1

WHILE ( @rows > 0 ) BEGIN

	INSERT INTO #recurseMap
	SELECT
		nm.[node]
		, rm.[treeDirection]
		, @level
	FROM
		#nodeMap AS nm
		JOIN #recurseMap AS rm ON rm.[node] = nm.[parent_node]
	WHERE
		rm.[level] = @level - 1

	SET @rows = @@ROWCOUNT
	SET @level = @level + 1

END

-- Results
SELECT
	@startNode AS [Start Node]
	, SUM(CASE WHEN [treeDirection] = 'L' THEN 1 ELSE 0 END) AS [Left]
	, SUM(CASE WHEN [treeDirection] = 'R' THEN 1 ELSE 0 END) AS [Right]
FROM
	#recurseMap

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

afroz
Starting Member

6 Posts

Posted - 2010-09-18 : 02:11:26

Thanx charlie your code really worked thats what i needed...

can u provide query with recursive functions (for 2008),i think these recursive functions are much faster than recursive while so..

any way thank u very much for your help..

afrozz..

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources