Trees in SQL

Say you want to make a Yahoo-like web directory, or something of that structure. You want to have top-level categories, and a variable depth of subcategories. How to represent this in the database?

I'm evaluating a couple of methods, and I would like some opinions. If you have used these structures for your own projects, let me know how they worked or didn't work for you.

Parent Tree

The traditional method is to have each tree node reference its parent. This way you can recursively dig back to the top of the tree, or recursively select all of its children. The trouble is that you can't do it in one statement, and you have to make several queries to get the whole picture.

Pro: dead simple to implement and understand, quick to INSERT/UPDATE the structure.
Con: cumbersome and slow to SELECT.

Nested Set Tree

Second method is called "nested sets." I read these articles by Joe Celko, and they are certainly interesting:
SQL for Smarties | March 96
SQL for Smarties | April 96
SQL for Smarties | May 96
SQL for Smarties | June 96

Looks very cool, but I'd like to know if this is used much in the real world. I'm sure it has its uses where it really excels, but is it right for my problem?

Some of those stored procedures make my head spin!

Mr. Celko points out that the parent tree is not normalized. Technically, I would have to defer to him, but consider this: generally speaking, normalization was devised so that information is not redundant and only needs to be updated in one place. With the above nested set tree, when you want to make an update, several (many, most) records in your tree need to be updated.

Pro: fast to SELECT.
Con: more difficult to implement and understand, slower to INSERT/UPDATE the structure.

Other idea

I considered having a "full path" string in each node. Something like a comma-separated list of ids:

"1,3,27,729,..."

This way, I get my path to root, and I can also select all of a node's immediate children by:
SELECT * FROM tree WHERE path LIKE '%27'

or all of its descendants by:
SELECT * FROM tree WHERE path LIKE '%27%'

The problem that I foresee here is when something needs to be moved. All of the desendants' paths would need to be updated, using a regex string replacement or something. I haven't thought this through, it might not be that bad, since moving a node would be a rare event: so what if it's slow.

Pro: easy to implement and understand, relatively quick to SELECT and INSERT
Con: slow to UPDATE the structure (not normalized).

"Mr. Celko points out that the parent tree is not normalized. Technically, I would have to defer to him, but consider this: generally speaking, normalization was devised so that information is not redundant and only needs to be updated in one place. With the above nested set tree, when you want to make an update, several (many, most) records in your tree need to be updated. "




It isn't entirely true that normalisation is used to make it so data only has to be updated in once place. It may be true that you only have to update data in one place within a small, non-complex structure, but for a larger structure with many branches, you're forced to update in multiple locations OR keep your normalisation to NF2 or less. Just something to think about

Of course... That's why I said "generally speaking" without wanting to get into a deep discussion on normalization. Let's be more productive and talk about real-world use of those trees I presented instead!

The point I wanted to make was that the academic notion of 3/4/5 NF isn't always the best solution, like the case of inserting nodes into nested set trees.

So, on the whole, "I agree!"

Celko himself wrote: "Normalization is like dating women who ride motorcycles. You might do it, but you don't tell your mother."

Actually... you can use just 1 select for that method... fetch all of the categories (with both their id and their parent id) and put them in an array.. you could then create a method that sorts them in the correct way and finds out what level the leaf is in

edit: here's a post I trew together some time ago: http://www.devarticles.com/forum/sh...=&threadid=1374

Hmm, pretty cool, thanks!

The only disadvantage I can see with your method is that you have to fetch the entire tree. For a large tree, that would be way too much if I only need a section.

Also, I found this excellent article on the topic which is PHP-specific and presents yet more ideas:

http://www.sitepoint.com/article/1105./1

I've recently needed to use trees on a few projects - and have gone with the single table, nodeid/parentid approach.

Because the tree's were used for navigation, I only needed to get the whole tree, so the issue of only "pulling out branchs" never came up. Just on that - it's no big deal add that functionality. If you go the nodeid/parentid approach, you would already have a recursive function that gathers child nodes, which accepts a beginning parentid as a parameter.

Aspnewbie referred me to a Stored Procedure that was essentially a duplicate of the ASP code I had written to gather the nodes. It was a bit of a brain bender!

I found that in order for the nav to be built quickly (i.e. gather the tree elements) I had to use Stored Procedures and arrays, because using inline SQL, and recordsets yielded pretty poor results (as aspnewbie is currently finding ).

Once the sites have been signed off, I'll post the URL's for them here.

Just found this post again, and as promised, here are a few sites I've recently completed that use a parent/child tree setup in the DB to generate the nav, and most of the content.

http://www.ingrealestate.com.au/investment/ (quite large)
http://www.ingrealestate.com.au/development/
http://www.gbcaus.org/greenstar/

Another one coming very soon.

What are your guys thoughts on the number of levels (i.e. depth) when using a tree for navigation. How many levels is too far, unusable?

Stumpy, could you post the code to the Stored Procedure you mentioned?

SELECTS will not be especially quick - like statements are nortoriously slow (they cannot be indexed easily).

Hadley

Hi,

Interesting post avit. I particularly like Joe celko's nested set idea, but has anybody else noticed the similarity between Joe and Ming the Merciless ?

URL Exhibit a (Joe Celko)

URL Exhibit a1 (Ming The Merciless)

That-Kid-Smith