Storing Hierarchical Data in a Database

[rident]

I was just browsing around and found this article. Great theories but why would you ever want to store hierarchical data in a flat database? Unless of course it was the only choice you had it seems like a bad idea to me. The first way takes too much system resources and the second has to have the tree rebuilt everytime you add a row to the table. Icky. I'd say this is the perfect situation for an XML database. An article that explores the XML database options for heirarchical data and php would be a great companion for this article. Anyone know of a good one?

[Dr Livingston]

XML does have it's uses, though in your point you could query the XML with XPATH though you'd be limited to that given data within the XML file, whereas you couldn't (easily) query the data in one XML file against another one, suchas product catelog and products.

Two seperate though interwinded entities that is where the database has the upperhand... relational data in other words.

On your last question, XML is a great technology... For distribution but not for performing queries. There are a number of XML databases out there, but I cannot see any benifit of using one over a relational database if all your going to do is to perform lookups/queries

[Courtney Miles]

The Modified Preorder Tree Traversal method solves a lot of the problems of the Adjacency list model but it also has a few of it's own.

When using a tree as the navigation of a website (or folders in Windows Explorer) you rarely see all branches of the tree at once. Rather, just the current node, child nodes, parent node, parent-siblings and so on back to root. So using food as an example, if the current node is Red you would see Food > Meat|Fruit > Yellow|Red > Cheery.

This isn't easy to do using the Adjacency list model either. But with the Adjacency list model you can easily query the children of a node (without getting grand children) and the siblings of a node. I can't see how to query the same with the traversal method so I will probably use a combination of the two methods unless someone can enlighten me.

[Sebastian Picklum]

@Courtney Miles: Explorer-Style? That can be done quite simply using the same technique.

First of all, you have to create Node-Groups. In our example case there would be the Groups (Food) (Fruit, Meat) (Red, Yellow) (Cherry) (Banana) (Beef, Pork).
Now add two more variables (e.g. "GroupLft" and "GroupRgt") to the database and use the Tree Traversal on the groups.
In our example, this would result in
1(Food)12 2(Fruit, Meat)11 3(Red, Yellow)8 4(Cherry)5 6(Banana)7 9(Beef, Pork)10
Your DB should now look like this
Name,Lft,Rgt,GroupLft,GroupRgt
================================
Food,1,18,1,12
Fruit,2,11,2,11
Meat,12,17,2,11
Red,3,6,3,8
Yellow,7,10,3,8
Cherry,4,5,4,5
Banana,8,9,6,7
and so on...

When you now Query "Cherry" by its Lft+Rgt-Values, you'll get the path. Querying by GroupLft+GroupRgt will get you a nice basement to build an "Explorer-Style"-menu.

About only getting children and _not_ grandchildren: Simply introduce a "depth" field. E.g.
Food=depth 0
Fruit,Meat=1
Red,Yellow,Beef,Pork=2

In combination with Lft and Rgt you are now able to choose how many "generations" of children you want to fetch.
(e.g. finding Children of Fruit, but not Grandchildren: SELECT * WHERE Lft>2 AND Rgt<11 AND Depth=(Depth_of_Fruit+1))

[Hendrix]

In response to Courtney's comment above. If you add an extra field called level, then you can find children by searching within the left/right values that a level of level + 1.

To find siblings you can just find all nodes with the same parent ID

There is an article about this here:

http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/index.html

[cassius42]

Using postgresql for a hierarchy, and I came up with this to find the immediate children of a node. Assuming that the parent node has:
nodeleft = $L
noderght = $R

<pre>
SELECT * FROM node AS a 
    INNER JOIN node AS b ON a.nodeid=b.nodeid 
    WHERE a.nodeleft>$L AND a.noderght<$R 
        AND (SELECT COUNT(nodeid) FROM node WHERE nodeleft<=b.nodeleft AND noderght>=b.noderght)=(SELECT COUNT(nodeid) FROM node WHERE nodeleft<=$L AND noderght>=$R)+1
    ORDER BY a.nodeleft ASC;
</pre>

First we have a table of all the children. In a separate table, we finds all nodes that are one level deeper than the parent node. We do this by first retrieving the path to the root, then counting the records in that path. Then it returns the common nodes of the two tables.

I don't know enough about PostgreSQL's internals to know how optimal this operation is. For a small number of nodes, it's trivial, but it would take a significant amount of time on a large set if PostgreSQL isn't smart enough to satisfy the first table first, which would significantly reduce the result set that it has to look at.

I haven't tried Weirdan's method (mentioned above) yet, because I don't understand it. If anyone has better, please post it.

[S]

This code simply doesn't work for me ...

[jakuza]

Very nice article. Thanks fo even just making me think again today. :)

[Peter]

Unfortunately, the method described in this article is incredibly inefficient.

[bionikal]

can someone list a practival use for this?
and explain why its inneficient

[annweb]

Hi ! .. I would like to know how could I make a node that would have many parents ...

Let's say I have this:

fruits

Apples

Oranges

Strawberry

Colored food

Red

Apples ( I want this to link to the other Apples )

Orange

Oranges (Same thing)

Black

How can I do that ? I'm really having a hard time trying to figure this out ! ... It must be me !

[w31rd0]

annweb,
By your description I understand you need to have two trees?
Or... you may need to add an extra property for every node (color property).

You can contact me on Y!M by sebastianvasile, I'll try to give you a hand.

Regards

[annweb]

Thanks w31rd0 !

But I found a way, about a week ago on how to do it with one table ... I just create a "ghost" category that will link to "apple" (for example) and that ghost category will be empty ... Then with a good MySQL headscratching command I call the actual apple category instead of the ghost !

Neet huh ! ?

Well I think it's neet !

[hubster]

Hi!

I would like to know how can I display my tree in a horizontal way just like the sample image used in the topic Modified Preorder Tree Traversal.

just like this image without the numbers:

[annweb]

Hello hubster !

I've decided to post the reply in the forum so that maybe it can help somebody else too !

Okay:

#1 You need to create a column in the table that you can call "link" and that column will be NULL for entries that have no link or will contain the ID of the entry that it's linked to.

Example:
ID|name|left|right|LINK
1|fruit|1|12|NULL
2|red|2|7|NULL
3|apple|3|4|NULL
4|strawberry|5|6|NULL
5|Delicious|8|11|NULL
6|GHOST LINKED TO STRAWBERRY|9|10|4


so this way you have
fruit

red

apple

strawberry

delicious

LINK TO STRAWBERRY

Then you need that magic MySQL command that gave me a 2 weeks headache:

SELECT table1.*, table2.link as link
FROM food as table1
LEFT JOIN food as table2
ON table1.id=table2.link
WHERE table1.link IS NULL
GROUP BY table1.id
ORDER BY table1.name

Will give you :

id name left right link link
0000003 apple 3 4 NULL NULL
0000005 delicious 8 11 NULL NULL
0000001 fruit 1 12 NULL NULL
0000002 red 2 7 NULL NULL
0000004 strawberry 5 6 NULL 4

Notice that you the category "Strawberry" but not the "Ghost category"

So that was my big pain for the last 2 weeks o if you use this code, don't be shy to give me credit for it !

I hope it was a good explanation !

[owarnes]

I have been experimenting using the Modified Preorder Tree Traversal example on sitepoint.

http://www.sitepoint.com/article/hie...-data-database

Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork

I was wondering if i could use this example to create a list <ul><li> etc for the output, but then I realised it was a bit more complex than I first thought.

Any thoughts

[Synchro]

Nice article. How might you store multiple independent trees? I'd like to avoid introducing a grouping field as it would make moving items between trees messy, plus surely much of the point is that which tree an item belongs to is implicit in knowing who its parent is. What's more, my trees don't have any semantic value - they are merely unnamed hierarchical collections with equal status. At present I have the obvious adjacency setup where independent trees are easily identified as they all start with items whose parent id is 0/NULL. Moving items between trees is trivial - just change the parent id pointer in the appropriate child. As far as I can see, the only way to handle this with preordering is to rebuild the two trees involved in their entirety, which can't be efficient. How can I parallel these operations using the preorder approach?

[bruin03]

I have been experimenting using the Modified Preorder Tree Traversal example on sitepoint.

http://www.sitepoint.com/article/hie...-data-database

Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork

I was wondering if i could use this example to create a list <ul><li> etc for the output, but then I realised it was a bit more complex than I first thought.

Any thoughts

I had the same question and it was answered here on Sitepoint.

http://www.sitepoint.com/forums/show...6&postcount=68

[Jiro]

Question:
Multi-User issues?

the whole
[quote]
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
[\quote]

should be locked. which would be very slow. hmm...

[voila]

how do i get the immediate children of 'Food' which are only 'Fruit' and 'Meat' by SQL?

[longneck]

how do i get the immediate children of 'Food' which are only 'Fruit' and 'Meat' by SQL?

select title from items where parent = 'Food';

[Sam]

Pretty not-well done.
Page 3 is just sth "i got rid of this article"
The explanation of how adding new nodes is very bad.
Sure explaining the easiest posibility is good, but try to add "Green" to the Fruit Stack. It could be a lot better explained how to get the values for the new node.

[chef]

uhm, add green to fruit would be : set lft for green value of rgt of fruit, increase all where rgt>=fruit.rgt + 2,set green.rgt to green.lft+1

not that complex, I agree setting parent id of green to fruit is easier, but as mentionned I can be worth the effort to test the performance of both systems...

[Data]

Does anyone have the code to insert a node, I can't believe the author of this article left that out. Please Help, I'm so confused.

[bigClown]

In playing around, here's the quick insert_node code I came up with. His description was pretty accurate, and I probably took the long way around a few hurdles, but it works.

function add_node($parent, $title) {
// first, we need to look at the right node of the parent. This will become the left node
// of the new child node (the right node of the new child will be left+1). Thus, the parent
// node's right value will be right+2. And each node, left or right, of a higher value than
// the parent's right needs to be incremented by two as well.

// First, get the parent node's right value.
$result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
$row = mysql_fetch_array($result);
$adjVal = $row['rgt']-1;
$newLeft = $row['rgt'];
$newRight = $row['rgt']+1;

// Now, we'll update each node with this right value or greater.
$result2 = mysql_query('UPDATE tree SET rgt=rgt+2 WHERE rgt>'.$adjVal.';');
$result3 = mysql_query('UPDATE tree SET lft=lft+2 WHERE lft>'.$adjVal.';');

// OK, now we just insert the node. Set values as appropriate - $lft to the parent's old $rgt
// and $rgt to the parent's old $rgt+1
$result = mysql_query('INSERT INTO tree (parent,title,lft,rgt) VALUES ("'.$parent.'","'.$title.'",'.$newLeft.','.$newRight.');');
}