#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Location
    United States
    Posts
    14
    Rep Power
    0

    Post 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.
  2. #2
  3. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Location
    United States
    Posts
    14
    Rep Power
    0

    update


    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.
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Location
    United States
    Posts
    14
    Rep Power
    0

    Also


    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.
  6. #4
  7. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    2
    Rep Power
    0

    Re: SQL parent/child tree query - please critique


    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):
    Code:
    id_project      description            id_parent     pname
    --------------------------------------------------------------------
    root                Root Project           root             root
    abc123            Development         root             Devel
    xyz098             Maintenance         root             Maint
    cmd003             Upgrades            xyz098          D123
    asd874             New Software      abc123          D847
    f8jk12               I9 Upgrades         cmd003          D234
    So, I will need the output to look similar to this

    Code:
    Root Project
         - Development
              - New Software
         - Maintenance
              - Upgrades
                   - I9 Upgrades
    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!
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Location
    United States
    Posts
    14
    Rep Power
    0
    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
  10. #6
  11. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Location
    United States
    Posts
    14
    Rep Power
    0
    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]
  12. #7
  13. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    2
    Rep Power
    0
    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
  14. #8
  15. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Location
    United States
    Posts
    14
    Rep Power
    0
    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).


    Originally posted by jwickham
    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

IMN logo majestic logo threadwatch logo seochat tools logo