SitePoint Sponsor

User Tag List

Page 1 of 6 12345 ... LastLast
Results 1 to 25 of 141
  1. #1
    ********* Articles ArticleBot's Avatar
    Join Date
    Apr 2001
    Posts
    1
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Article Discussion

    This is an article discussion thread for discussing the SitePoint article, "Storing Hierarchical Data in a Database"

  2. #2
    Rajesh Garg
    SitePoint Community Guest
    Thanks for writing a great article and nice explaining the complex topic.

    The Modified Preorder traversal method works if there is a one to one parent child relationship. If a node could be a child to other parents then this does not work, because then depending on which parent the child belongs to, the left and right values will vary. Please let me know if that's not the case.
    Thanks
    Rajesh Garg
    rajesh.garg@comac.com

  3. #3
    SitePoint Member dhoran's Avatar
    Join Date
    Sep 2001
    Location
    Rochester, NY
    Posts
    23
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Great explanation of a potentially complex topic. Great job!

  4. #4
    Anonymous
    SitePoint Community Guest
    Great work. Saved me a lot of stress.

  5. #5
    lloyd monteiro
    SitePoint Community Guest
    how effective is it if i delete or add a new node and there are 1000 of records, wont he reupdate of the left and right numbers be slow??

  6. #6
    LoreZyra
    SitePoint Community Guest
    Excellent Explaination! However the update query should be: UPDATE tree SET rgt=rgt+2 WHERE rgt>=5;
    UPDATE tree SET lft=lft+2 WHERE lft>5;

    When I first read this article, I didn't understand how the 5 in the previous query was determined. Was it calculated from the right value of the parent node (minus one)?

  7. #7
    GJ
    SitePoint Community Guest
    Great article! But how would you find the direct children of a node (by means of only the left and right key)? E.g the direct children of fruit are red and yellow...Thnx!

  8. #8
    Dirkjan
    SitePoint Community Guest
    Great article, and that numbering system is a great solution, but i DO use your first (simple) system. The difference is that I cache the html which is created. So all those querys have to run only when editting/adding/deleting items from the data :)

  9. #9
    AndreaTivoli
    SitePoint Community Guest
    The article is well written. Thanks Gijs.

    The only thing I miss is, that it speaks only about inserting a leaf node (i.e. a node without children). What if I want to insert a new node "color" as a child of "Fruit" and I want "Red" and "Yellow" be children of "Color"?

    My proposal:
    UPDATE tree SET lft=lft+1 WHERE lft BETWEEN 3 AND 10
    UPDATE tree SET rgt=rgt+1 WHERE rgt BETWEEN 3 AND 10
    and the rest as proposed in the article:
    UPDATE tree SET rgt=rgt+2 WHERE rgt>10
    UPDATE tree SET lft=lft+2 WHERE lft>10

    3 is the lft-value of the first direct child of the new node ("Red"), 10 is the rgt-value of the last direct child of the new node ("Yellow").

  10. #10
    AndreaTivoli
    SitePoint Community Guest
    To LoreZyra:

    I don't see why the update should be >=5 instead of >5. I think the statement in the article is correct.

    If you use the rgt-value of the parent-node minus 1, it works only if you insert a new leaf to the right of all other leafs (as in the article). But not, if you want to add "Blue" between "Red" and "Yellow".

    If 5 is the lft-value of the new node you insert minus 1, then it works allways (no mather where you insert the new leaf).

  11. #11
    SitePoint Enthusiast ryushe's Avatar
    Join Date
    Aug 2004
    Location
    NL
    Posts
    68
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi, 'm using the first version at this moment as I have a many-to-many relation in my DB. So my question might be a bit stupid, but can anyone explain to me how I can have the first level horizontal, and the second layer under that one (also horizontal), etc etc?
    Also how to make a visual indicator (link color change) which item is active?

  12. #12
    SitePoint Zealot David C's Avatar
    Join Date
    Nov 2003
    Location
    New York!
    Posts
    105
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Do you mean horizontal in the sense of presentation? If so, the DB query probably wouldn't change, it would be done with HTML/CSS.

  13. #13
    SitePoint Enthusiast ryushe's Avatar
    Join Date
    Aug 2004
    Location
    NL
    Posts
    68
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yes, presentation wise. Problem is, the main "browser" I'm creating this for does not (yet) understand CSS, and at most basic html tags, although no table tags yet.
    I "need" something like:

    parent1 | parent2 | parent3
    child 1 | child 2 | child 3 | child 4
    subchild 1 | subchild 2

    I've been playing around with creative < b r / > placements, but no luck yet. Only option I see is to make a duplicate function which is triggered by a var passed onto it to activate sublevel. Of course this should be able to be done without creating extra functions I'd say. Any suggestions?

  14. #14
    SitePoint Member
    Join Date
    Sep 2004
    Location
    california
    Posts
    0
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi --
    Does anybody know the proper mean to "MOVE" a node using the modified preorder tree traversal? I would like to move an node and all of its children to a new parent node.
    Thanks

  15. #15
    Non-Member Big Fat Bob's Avatar
    Join Date
    Sep 2004
    Location
    United Kingdom (Come)
    Posts
    79
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yo

    You might find this thread interesting then

    http://www.sitepoint.com/forums/showthread.php?t=186601

  16. #16
    Niels
    SitePoint Community Guest
    Hi,
    how do you select just the first child level with this method? I now solved it in PHP. But i'd rather not select them at all ( performance wise )

  17. #17
    SitePoint Member
    Join Date
    Jul 2003
    Location
    Somewhere far beyond
    Posts
    1
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Niels
    Hi,
    how do you select just the first child level with this method? I now solved it in PHP. But i'd rather not select them at all ( performance wise )
    Friend of mine asked similar question, here's what I came up with:
    Code:
    SELECT 
        CONCAT( REPEAT('   - ', COUNT(*) ), 
                          t1.Name, 
                          '  (', 
                          t1.l, 
                          '|', 
                          t1.r, 
                          ')' ) AS v 
        FROM t AS t1, 
            t AS 2, 
            t AS t3 
        WHERE t1.l BETWEEN t2.l AND t2.r 
        AND   t2.l BETWEEN t3.l AND t3.r 
        AND   t3.l=2   /*  <=== node to start with   */
        GROUP BY t1.l 
        HAVING count(*) = 2 /* <=== show only direct descendats */
    with just three joins one can get any slice of the entire tree (or particular branch). Count(*) equals to node level relative to the level of 't3.l'.

  18. #18
    SitePoint Member
    Join Date
    Nov 2004
    Location
    MyVille
    Posts
    3
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Wow. This is great. Just what I was looking for. I also like the thread Big Fat Bob posted - thanks!

    One question...

    Any way I can sort the results alphabetically? It looks like, from the functions in this article and others I have seen, you have to ORDER BY the lft ID. Does the data have to be inserted/updated into the database and placed in the appropriate spot alphabetically for this to work? This will be cumbersome with the amount of inserts/updates.

    What I am building is a large document management system that basically will display a "Windows Explorer" type of folder tree. But the tree needs to be alphabatized as well as follow the lft ID so the data stays as a "tree".

    Thanks for any tips!

  19. #19
    SitePoint Member
    Join Date
    Nov 2004
    Location
    MyVille
    Posts
    3
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by caffeinerusher
    Hi --
    Does anybody know the proper mean to "MOVE" a node using the modified preorder tree traversal? I would like to move an node and all of its children to a new parent node.
    Thanks
    Take a look at the post from Widow Maker at the link Big Fat Bob posted (http://www.sitepoint.com/forums/showthread.php?t=186601).

    Toward the middle of the post is a great Tree class and includes a function for what you are trying to do.

  20. #20
    Google Engineer polvero's Avatar
    Join Date
    Oct 2003
    Location
    Mountain View
    Posts
    567
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi there.
    I've been working on this problem for a few days now...
    If anyone can answer this, it would be a huge help.
    In the midst of creating a photo gallery with unlimmited sub categories...how can I find a parent's ID provided that I have a subcategory ID.

    For example,
    PHP Code:
    function get_parent_id $sub_cat_id )
    {
    // process, process...
    return $parent_id;

    my table looks like this
    Code:
    ID | Name | Lft | Rgt | ParentID
    Anyone? I'm even willing to give a small donation or whatever...

    Thanks a bunch,
    Dustin

  21. #21
    Google Engineer polvero's Avatar
    Join Date
    Oct 2003
    Location
    Mountain View
    Posts
    567
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Me again.
    Brain Fart.

    I played around a bit more and came up with this.

    PHP Code:
    <?php
    class find_parent
    {
    var 
    $id;
    var 
    $left;
    var 
    $right;
        function 
    find_parent $id )
        {
        
    $this->id $id;
        
    $q mysql_query("select m_c_left,m_c_right from multimedia_category where m_c_id='$this->id'");
            while ( 
    $r mysql_fetch_array($q) ) 
            {
            
    $this->left $r['m_c_left'];
            
    $this->right $r['m_c_right'];
            }
        }
        function 
    get_values ()
        {
        
    $qq mysql_query("select m_c_left,m_c_right,m_c_id from multimedia_category where m_c_right > '$this->right'
        and m_c_left < '
    $this->left'
        order by m_c_left desc limit 1"
    );
            while ( 
    $rr mysql_fetch_array($qq) )
            {
            return 
    $rr['m_c_id'];
            }
        }
    }
    ?>

  22. #22
    IMac
    SitePoint Community Guest
    Using PostgreSQL, you can store the hierarchical path for each node in an array of smallints:

    create table treedata (
    id integer not null primary key,
    node smallint[] not null,
    name text not null
    );

    insert into treedata values (1, '{0}', 'Food');

    insert into treedata values (2, '{0,0}', 'Fruit');

    insert into treedata values (3, '{0,0,0}', 'Red');

    insert into treedata values (4, '{0,0,0,0}', 'Cherry');

    insert into treedata values (5, '{0,0,0,1}', 'Strawberry');

    insert into treedata values (6, '{0,0,1}', 'Yellow');

    insert into treedata values (7, '{0,0,1,0}', 'Banana');

    insert into treedata values (8, '{0,1}', 'Meat');

    insert into treedata values (9, '{0,1,0}', 'Beef');

    insert into treedata values (10, '{0,1,1}', 'Pork');

    To retrieve, just SELECT FROM treedata ORDER BY node ASC;

    To retrieve a branch: SELECT FROM treedata WHERE node[1:3] = '{0,0,0}';

    This retrieves 'Red' and its children.

    Updating is simply a matter of saying: UPDATE datatree set node[3] = 2 WHERE node[1:3] = '{0,0,0}';

    This puts 'Red' after 'Yellow'.

    Hope this helps.

  23. #23
    IMac
    SitePoint Community Guest
    Just further to my post about PostgreSQL arrays, you can easily find all the immediate children of a node too:

    SELECT * FROM treedata WHERE node[1:2] = '{0,0}' AND node[4] IS NULL;

    This retrieves 'Red' and 'Yellow', but not their children.

  24. #24
    IMac
    SitePoint Community Guest
    Just further to my post about PostgreSQL arrays, you can easily find all the immediate children of a node too:

    SELECT * FROM treedata WHERE node[1:2] = '{0,0}' AND node[4] IS NULL;

    This retrieves 'Red' and 'Yellow', but not their children.

    Can you easily retrieve just the *immediate* children of a given node via modified pre-order tree traversal?

    Suppose you want a series of web pages to walk down a tree, so that each page displays just a node and its immediate children (each child linking to a page that displays it and *its* children)?

    One dynamic web page could handle this recursive algorithm with my array-based tree quite easily and efficiently.

  25. #25
    IMac
    SitePoint Community Guest
    Sigh!

    Sorry, make all those queries with SELECT FROM... into SELECT * FROM...

    It is hard writing comments in such tiny text fields!


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •