SitePoint Sponsor

User Tag List

Page 1 of 5 12345 LastLast
Results 1 to 25 of 103
  1. #1
    Sidewalking anode's Avatar
    Join Date
    Mar 2001
    Location
    Philadelphia, US
    Posts
    2,205
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Storing Hierarchical Data in a Database

    This forum thread discusses the SitePoint article 'Storing Hierarchical Data in a Database' by Gijs Van Tulder.

    "Whether you want to build your own forum, publish the messages from a mailing list on your Website, or write your own CMS: there will be a moment that you’ll want to store hierarchical data in a database. Gijs explains two practical methods to do just that."

  2. #2
    Sidewalking anode's Avatar
    Join Date
    Mar 2001
    Location
    Philadelphia, US
    Posts
    2,205
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Fantastic article. I'd really like to see more stuff along these lines, delving into the computer science side of things without being too baffling.
    TuitionFree — a free library for the self-taught
    Anode Says...Blogging For Your Pleasure

  3. #3
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Not a bad article anode - cheers for pointing it out 8)

    Like the idea of using left and right to navigate the database - now just need to find the time to read it more and see what I can see aye ?

  4. #4
    SitePoint Wizard samsm's Avatar
    Join Date
    Nov 2001
    Location
    Atlanta, GA, USA
    Posts
    5,011
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I believe the left and right technique is typically refered to as "nested-set" method. I like that graphic the author used, quite clear.

    Here's another source on pretty much the same info: A Look at SQL Trees

    This artcle provides some counterpoint: More Trees & Hierarchies in SQL

    And here's a thread where Vincent blows my mind by bringing it up: http://www.sitepointforums.com/showt...threadid=86795 ;-)
    Using your unpaid time to add free content to SitePoint Pty Ltd's portfolio?

  5. #5
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks... I'll have a look at some point this week 8)

  6. #6
    SitePoint Member
    Join Date
    Apr 2003
    Location
    CA
    Posts
    1
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Excellent article - addresses questions I've had in my code. One question though: I'm using the adjacency list model to store threads in a message forum, and despite it's drawbacks, I can store multiple threads as separate trees in the same table - the root of each thread has no parent. When I want to add a new node (msg) to a particular thread, I only need to insert the row and set it's parent. With Modified Preorder Tree Traversal, when I add a new row, I have to rebuild the entire table, even if I'm just modifying a sub-tree.
    So, in a tree where most nodes have several siblings (like a forum with shallow but long threads), isn't the Adjacency List model just as efficient?
    Also, is recursion and multiple SELECTs during retrieval truly less efficient than multiple cascading UPDATEs during insertion? What about in forums where posts are nearly as common as reads? (I'm not arguing one way or the other, just curious if the cost of recursion in PHP, ASP, or whatever has been measured.)
    Thanks!

  7. #7
    SitePoint Guru nagrom's Avatar
    Join Date
    Jul 2001
    Location
    Western CT, USA
    Posts
    803
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    great article.

    here's yet another method, based on one of the methods described in the evolt article cited by the author:
    http://www.morgankelsey.com/code/multi-threaded_board/

    this actually addresses message boards, bhoman, so it might help you.

    yes, the method i use, and celko's method, yield a far more complicated INSERT than the adjacency model. however, what is the database doing all the time? probably displaying, not inserting. the adjacency model is the most "correct", but it's not the best for the internet (IMHO)

  8. #8
    SitePoint Member Spiff Dog's Avatar
    Join Date
    Jun 2002
    Posts
    20
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Couldn't you just build a recursive Stored Procedure to pull the data for you? It's much faster that way and easier to port.

    If you write the procedure right, you get the speed of a stored proc plus the benefit of pulling only the records you need. Then it's just a matter of looping over a recordset or binding to an object (in the case of ASP.NET).

    -Spiff Dog
    Last edited by Spiff Dog; Apr 30, 2003 at 11:56.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    "Home is where you hang your @."
    Spiff Dog Design

  9. #9
    SitePoint Evangelist ucahg's Avatar
    Join Date
    Apr 2001
    Location
    Sarnia, Ontario, Canada
    Posts
    434
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    How about a self-join, as in this article found at devshed: http://www.devshed.com/Server_Side/M...ins/page9.html

    From what I can tell, this would do the same thing, and is simple to understand.

  10. #10
    ********* Member website's Avatar
    Join Date
    Oct 2002
    Location
    Iceland
    Posts
    1,238
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Oh this is great! All the questions that popped up my mind during the reading were all answeared a few lines below.

    But talking about how inserts are inefficient, isn't it enough just to raise the level of rgt and lft by one on nodes that have rgt and lft higher then the desired one? or didn't I read it carefully enough?
    - website

  11. #11
    SitePoint Guru
    Join Date
    Oct 2001
    Posts
    656
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hmm, website, I think you are right. Just 'shifiting up' all lft and rgt values by two would do the job to 'make room' for the new node would work, I think.

    I like this approach for storing hierarchical data, it would be far more efficient than the recursive approach when it comes to SELECTs It's also a nice maths puzzle to think about efficient ways of manipulating the tree..

    edit: woops, turns out we both read over the article too fast, increasing lft and rgt by two is exactly how it's done..

  12. #12
    SitePoint Guru nagrom's Avatar
    Join Date
    Jul 2001
    Location
    Western CT, USA
    Posts
    803
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    yes, the trick is finding the proper insertion point.

  13. #13
    ********* Member website's Avatar
    Join Date
    Oct 2002
    Location
    Iceland
    Posts
    1,238
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    edit: In reply to Captain Protons post

    ok, that is nice, but I guess making an administartion system to add sub and side (perhaps forums) is rather hard since it is different from what number all is raised.

    Does anyone know how eg vBulletin does their tree, to they use this method ?
    - website

  14. #14
    ********* Member website's Avatar
    Join Date
    Oct 2002
    Location
    Iceland
    Posts
    1,238
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by nagrom
    yes, the trick is finding the proper insertion point.
    exactly!!! with some automated system that might not be as easy as saying it.
    Last edited by website; Aug 30, 2003 at 18:33.
    - website

  15. #15
    SitePoint Zealot Mr Chocolate's Avatar
    Join Date
    May 2002
    Location
    Australia
    Posts
    116
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    That was a great article! I am having a problems with the code provided. has any one tested the code? I'm getting a blank screen no errors just white space. i created a database with all the exact data. [img]images/smilies/frown.gif[/img]

    Edit:

    Modified Preorder Tree Traversal code
    Last edited by Mr Chocolate; Apr 30, 2003 at 20:47.

  16. #16
    SitePoint Wizard wdmny's Avatar
    Join Date
    Jul 2000
    Location
    Here
    Posts
    1,010
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The method on the morgankelsey.com link is the same idea I used awhile back when writing a threaded system myself. While the article was good, I think this method is probably easier to handle than the right and left idea.

  17. #17
    SitePoint Member
    Join Date
    Apr 2003
    Location
    the Netherlands
    Posts
    6
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by website
    ok, that is nice, but I guess making an administartion system to add sub and side (perhaps forums) is rather hard since it is different from what number all is raised.
    Is it really that hard? After all, you'll need the parent's id even if you're using the recursive approach. With that id, you just need one extra query to get the numbers you need.

    Quote Originally Posted by Mr Chocolate
    I am having a problems with the code provided. has any one tested the code? I'm getting a blank screen no errors just white space. i created a database with all the exact data.
    It may sound silly, but did you actually run the function? Just copying the display_tree() function from the article isn't enough. You need to execute it with:
    PHP Code:
    display_tree(''); 

  18. #18
    blonde.... Sarah's Avatar
    Join Date
    Jul 2001
    Location
    Berkshire, UK
    Posts
    7,442
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    No the code from the first page doesn't actually work! I can't understand how people can write these articles without testing the code that they are displaying! Its a good subject but ruined because you can't get past the first page!!

    Mr Chocolate use this code:

    dB code (need to ensure you use NOT NULL for parent)

    Code:
    drop database heir;
    
    create database heir;
    
    use heir;
    
    create table tree (
    parent varchar(100) not null,
    title varchar(100)
    );
    
    insert into tree set title="Food";
    insert into tree set parent = "Food", title="Fruit";
    insert into tree set parent = "Fruit", title="Green";
    insert into tree set parent = "Green", title="Pear";
    insert into tree set parent = "Fruit", title="Red";
    insert into tree set parent = "Red", title="Cherry";
    insert into tree set parent = "Fruit", title="Yellow";
    insert into tree set parent = "Yellow", title="Banana";
    insert into tree set parent = "Food", title="Meat";
    insert into tree set parent = "Meat", title="Beef";
    insert into tree set parent = "Meat", title="Pork";
    revised function code

    PHP Code:
    function display_children($parent$level) { 
       
    // retrieve all children of $parent 
       
    $result mysql_query("SELECT title FROM tree WHERE parent='".$parent."'"); 

       
    // display each child 
       
    while ($row mysql_fetch_array($result)) { 
           
    // indent and display the title of this child 
           
    echo str_repeat('& n b s p ; & n b s p ; & n b s p ; ',$level).$row['title']."\n<br>"

           
    // call this function again to display this 
           // child's children 
           
    display_children($row['title'], $level+1); 
       } 


    display_children('',0); 
    (I have changed the $result part to say mysql_query not mysql_result)

    This will now display what is mentioned in the article..

    Rant over I will now continue to read the article, if I spot any other errors I will post them here so others can work it also

    Sarah

    Edit:

    it displays better with the & n b s p ; without the spaces for the display part
    Regular user

  19. #19
    blonde.... Sarah's Avatar
    Join Date
    Jul 2001
    Location
    Berkshire, UK
    Posts
    7,442
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    for second part on the first page use this (otherwise I just got a blank)

    PHP Code:
    <?php 
    // $node is the name of the node we want the path of 
    function get_path($node) { 
       
    // look up the parent of this node 
       
    $result mysql_query("SELECT parent FROM tree WHERE title='".$node."'"); 
       
    $row mysql_fetch_array($result); 
       
    // save the path in this array 
       
    $path=array();
       
    // only continue if this $node isn't the root node (that's the node with no parent) 
       
    if ($row['parent']!='') { 
           
    // the last part of the path to $node, is the name of the parent of $node 
           
    $path[] = $row['parent']; 
           
    // we should add the path to the parent of this node to the path 
           
    $path array_merge(get_path($row['parent']), $path); 
       } 
       
    // return the path 
       
    print_r($path);
            echo 
    "<br>";
       return 
    $path;

    get_path('Cherry'); 
    ?>
    Regular user

  20. #20
    SitePoint Member
    Join Date
    Apr 2003
    Location
    the Netherlands
    Posts
    6
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi Sarah,

    Thank you for checking my code. While I already tested the scripts myself, I clearly didn't test enough. Especially the first error, mysql_result instead of mysql_query, is a very stupid error that shouldn't have been made. While the function did work at some point, it now clearly doesn't. I humbly apologize for that big mistake. Using &nbsp; instead of simple spaces is also a good idea.

    The second error, however, isn't really an error. The function in the article does work, but it doesn't output anything itself. When called, the get_path($node) function returns an array. You need to display that yourself. Instead of putting print_r() and echo in the function, you could run it with:

    PHP Code:
    print_r(get_path('Cherry')); 
    And that should give you the path to Cherry.

    Quote Originally Posted by Article
    To get the path to 'Cherry', you run: get_path('Cherry'); You'll then get an array that contains the path. If you use print_r() to display this array, you’ll see:
    That you should use print_r() to display the path is mentioned in the article, just after the get_path() function on the first page. However, I now agree with you that it's not clear enough. Especially the sentence that you should run "get_path('Cherry');" to get the path, makes it very confusing. It would've been better if I'd written: "To display the path to 'Cherry', you run: print(get_path('Cherry'));"

    I'll e-mail SitePoint to see if they can correct the article.

    Sorry for the inconvenience,

    Gijs

  21. #21
    SitePoint Zealot Mr Chocolate's Avatar
    Join Date
    May 2002
    Location
    Australia
    Posts
    116
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    thanks sarah & gvtudler,

    That's great you spotted the mistake in the first lot of code i did'nt even have a look at that. i was much more interested in the second part of the article which was great gvtudler well done! I guess i should have read the article better i just jumped straight in and even before i had finshed your article i had already tested the code and db design. I can now see the path to cherry thank you very much. I always thought sitepoint would test the article before they published it, any way that was a great article! an it has a reader rating of 9.5 that's great!

  22. #22
    SitePoint Guru nagrom's Avatar
    Join Date
    Jul 2001
    Location
    Western CT, USA
    Posts
    803
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    here's yet another different method:
    http://www.sqlteam.com/item.asp?ItemID=8866

    --not to detract from the article or anything, i just think it's interesting to see all the different solutions.

  23. #23
    SitePoint Wizard samsm's Avatar
    Join Date
    Nov 2001
    Location
    Atlanta, GA, USA
    Posts
    5,011
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by nagrom
    here's yet another different method:
    http://www.sqlteam.com/item.asp?ItemID=8866
    Take a gander at the links in post 4. ;-)

    Well, I agree that is an interesting article.

    However, like nested set method, it looks like it too suffers from "difficult update disease". Change the root, and you have to update lineage for the entire table. Not the easiest update in the world either!
    Using your unpaid time to add free content to SitePoint Pty Ltd's portfolio?

  24. #24
    blonde.... Sarah's Avatar
    Join Date
    Jul 2001
    Location
    Berkshire, UK
    Posts
    7,442
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    gvtulder,

    Thats for popping in a saying hi - I am afraid that I have not yet managed to get any further than that first page - purely ran out of work.

    It would certainly be ncie if the code could be updated.

    As for the print_r part - yes I spotted that you had said it in eth example but I still couldn't get it to echo out with out putting something adidtional in the function - anyway its not supposed to return anything so that is cool.

    Also if you are getting SP to update the code I also removed the ; from inside the SQL query and also changed around the quotes as it brought up an error with ' not " and visa versa

    I will certainly read the rest of the article eventually as I am very interested in thing new like this.

    I think I was just having a bad day on friday so if my comments seemed a little harsh then I apologise

    Sarah
    Regular user

  25. #25
    ********* Member website's Avatar
    Join Date
    Oct 2002
    Location
    Iceland
    Posts
    1,238
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hello again

    I am wondering about this tree, your function uses echo() function to print out the tree, I am using templates for all my content so it would be nice if there was any way to stick this tree inside an array or something which I could then loop through, is this possible? I have been thinking about the structure of the array though, here is an idea:
    PHP Code:
    Array (
        [
    name] => SomeTopTreeName;
        [
    id] => {theIdInTheDB};
        [
    subtree] => Array(
            [
    name] => SomeSubTreeName;
            [
    id] => {theIdInTheDB};
            [
    subtree] => Array(
                
    etc...
            )
        ) 
    just an idea though, but please can anyone post a good way to store the tree in an array for later usage!

    Thanks in advance.
    - website


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
  •