SQL parent/child tree query - please critique

I couldn't find an elegant answer to this problem either, so I made my own. It isn't a single query but the overhead seems fairly low. The key is to provide a sort key for sorting the records according to their position in the tree structure. Here's what I got:

First, I use a stored procedure. The stored procedure will drill down to the Nth level given a parent ID. Not exactly a single query but still simple to implement. In this examble, I assume both parent and child IDs are ints and that the source table is called tb_tree (parent_id int NOT NULL, child_id int NOT NULL) so...

--We'll call the SP "sp_GetKids"

CREATE PROCEDURE sp_GetKids(@parent_id as int)
AS
SET NOCOUNT ON

/*We'll declare a temp table to store our results, we have a unique ID, the node's id, a tier_cnt to identify the tier level (not essential for output but critical for building the results table) and the ALL IMPORT lineage_id. What is the lineage_id that? This is what you will sort on when your temp table is complete! It will build a line of numerals, each discribing the node's ancestry and map to its root. Cool eh? */

Declare @table TABLE(
ID INT INDENTITY(1,1) NOT NULL,
node_id int null,
tier_cnt int NULL,
lineage_id varchar(50))

/* declare our tier cnt integer, and set it to two (for the number of tiers existing in the temp tabel for for our Nth level loop */
Declare @tier as int
SET @tier = 2

/* Let's build the root level This inserts the root level into the temp table */
INSERT INTO @table (node_id,tier_cnt,lineage_id)
VALUES(@parent_id,1,'1')

/*
Now we must go get for first batch of children (if there are any)
*/

INSERT INTO @table
Select child_id,2,'1' from tb_tree where parent_id = @parent_id

/*
Now comes the magic- believe it or not. We need to stamp our newly added children with their genetic code, so to speak. Each line item is given a map back to its the top level parent via the lineage_id
*/

UPDATE @table set lineage_id = lineage_id+LTRIM(STR(ID)) WHERE len(lineage_id) < tier_cnt

/*Now the table is initalized and ready for the Nth level iterations. So we start a while loop using the SQL Server's @@rowcount (i'm not sure what this variable is called in other platforms but I'm sure a rows affected variable should be available) . We also have our @tier int set to 2 (we've added two other tiers already, so that's the current tier).*/

WHILE @@rowcount > 0
BEGIN
SET @tier = @tier+1
/*Go get children nodes for the next tier that are not already accounted for */

INSERT INTO @table (node_id,tier_cnt,lineage_id)
SELECT child_id, @tier,(select lineage_id from @table where node_id = parent_id)
FROM tb_tree
WHERE parent_id IN (select node_id from @table)
AND node_id NOT in (select node_id from @table)

/* Now stamp the lineage ID with last numeral, the ID field asigned to the new nodes */
UPDATE @table set lineage_id = lineage_id+LTRIM(STR(ID)) WHERE len(lineage_id) < tier_cnt
END

/* The loop end once no more related children can be found. So, with all the children added we need only select the temp table ordered by the lineage_id for teh SP's result*/

select * from @table order by lineage_id
GO


That's it. Now you can have the line items return in the tree order. Plus, the tier_cnt and be used in application logic to shift cells to the right in order to place item according to their placement in the tree.

The "line" column routine falls apart after ten nodes u sing a length function. Instead, build the line with delimited values (1)(2)(3).

UPDATE line set line=line+'('+ltrim(str(ID))+')' where line not like '%('+ltrim(str(ID))+')%'

this checks to see the line item's node has been added to the end of it's own line. If it hasn't, it's updated to included it.

Also... If you add an ID column to the tree table, no need to build it in the temp table as an identity column. But that may be a preference.

I have a couple of questions with your syntax.

First off you are declaring this temporary table to store the results. What does the INDENTITY(1,1) do for the ID column? When I tried to compile your code SQL Query Analyzer it bombed mon that line.

Declare @table TABLE(
ID INT INDENTITY(1,1) NOT NULL,
node_id int null,
tier_cnt int NULL,
lineage_id varchar(50))

Also do you think it will be just as simple to use this procedure if the child_id and parent_id are varchars instead of integers?

I am having to do a parent-chile tree report on some projects.

My table structure is as follows:

id_project varchar
description varchar
id_parent varchar
hours_estimate float
percent_complete float
creator varchar
loggable varchar
pname varchar (project name)

The parents and childern are in this same table. For instance the table could look like this(just including the columns of importance with sample info):


So, I will need the output to look similar to this



Any ideas would be appreciated. I have tried to implement your procedure with this table, but I guess I do not understand it fully and I am not catching all of the integre declarations and it is trying to typecast the strings into the integers and then it is blowing up when I try to run the procedure. From what I can tell it doesn't go more than three tiers deep, but there is a possibility that it could.

Thank you very much!

IDENTITY tells SQL server to use the column as an "auto number" column IDENTITY(seed value, increment amount).

I don't think it's necessary that the ID's be INTs but if they are not, you will have to account for the considerable syntax differences between my interger based example and a string based version.

If the procedure was run against your example table the basic results would look something like this

id_project description lineage
-----------------------------------------------------------
root Root Project root
abc123 Development rootabc123
xyz098 Maintenance rootxyz098
cmd003 Upgrades rootxyz098cmd003
asd874 New Software rootabc123asd874
f8jk12 I9 Upgrades rootxyz098cmd003f8jk12
--------------------------------------------------------------------------------

The key is this so called Lineage column, see how it is made of IDs that trace each node back to it's root. You select these rows, sorting on this value and your tree is built for you. I suppose if the table was small enough, you could simply maintain these values by hand directly in the table and be done with it.

I'll try to forward a more readable code example as time allows.

Thanks,
Tatero

Oh yeah, it's good to read my own debug replies too, the lineage column's ID's should be delimited, like: [root][xyz098][cmd003][f8jk12]

Sorry about the questions, but I have one more question. Your follwing code is as follows:

INSERT INTO @table (node_id,tier_cnt,lineage_id)
SELECT id_project, @tier,(select lineage_id from @table where node_id = parent_id)
FROM tb_tree
WHERE parent_id IN (select node_id from @table)
AND node_id NOT in (select node_id from @table)

So when I attempt to put my projects table into this insert statement it blows up.

INSERT INTO @table (node_id,tier_cnt,lineage_id)
SELECT id_project, @tier,(select lineage_id from @table where node_id = id_parent)
FROM projects
WHERE id_parent IN (select node_id from @table)
AND id_project NOT in (select node_id from @table)

Does this look correct?? I get the following error:

Server: Msg 446, Level 16, State 9, Procedure sp_GetKids, Line 46
Cannot resolve collation conflict for equal to operation.



Thanks again!

-Jeremy

In your project's table, you have a collation set on a text column that is NOT the database default (applied to your temp table). In SQL 2000, you can blank-out the collation setting (in the design table mode) and the collation will reset to <database default>. This should make the error go away. Or you can modify the collation in your procedure ... blah blah blah where id_parent COLLATION SQL_Latin1_General_CP1_CI_AS = node_id ...

A lot of times, you'll see SQL_Latin1_General_CP1_CS_AS in these situation in the table's design mode. Which the ...CS... means CASE SENSITIVE. This is usually not good. SQL_Latin1_General_CP1_CI_AS where the ...CI... means CASE INSENTITIVE is usually better and is typically the <database default> anyway. Perhaps you imported these table from another database and the collation settings where not the same default. This can be desirable in some cases (like Healthcare codes where 'M' is one thing and 'm' means another).