Storing Hierarchical Data in a Database

[anode]

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."

[anode]

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.

[Dr Livingston]

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 ?

[samsm]

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 ;-)

[Dr Livingston]

Thanks... I'll have a look at some point this week 8)

[bhoman]

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!

[nagrom]

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)

[Spiff Dog]

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

[ucahg]

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.

[website]

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?

[Captain Proton]

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..

[nagrom]

yes, the trick is finding the proper insertion point.

[website]

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]

yes, the trick is finding the proper insertion point.

exactly!!! with some automated system that might not be as easy as saying it.

[Mr Chocolate]

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

[wdmny]

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.

[gvtulder]

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.

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:

display_tree(''); 

[Sarah]

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)

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

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

[Sarah]

for second part on the first page use this (otherwise I just got a blank)

<?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'); 
?>

[gvtulder]

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   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:

print_r(get_path('Cherry')); 

And that should give you the path to Cherry.

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

[Mr Chocolate]

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!

[nagrom]

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.

[samsm]

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!

[Sarah]

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

[website]

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:

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.