hiearchical structures?

Anon

Hello all.

Question... I have put together a hiearchical structured table...it is used to group products into categories, subcategories, subsubcategories, etc.

My Categories table is set up as such: CategoryID, CategoryLevel, CategoryName, ParentID. Where CategoryID is the PK, CategoryLevel tells me if it is a category, subcategory, subsub, etc, and ParentID is the categoryID of that category's parent.

Ok, here's my question. I am trying to run a report that will give me the entire hierarchical structure of a product. So it needs to show Category, SubCategory, etc... But I only really know how to show the lowest level (I have a table ProductsCategories that has columns ProductID and CategoryID).

Can you tell me how to report the entire structure? I am new to db design, but I do think I set up the tables correctly.

I am using Access2000, but even if you tell me the SQL statements I'd be happy (but happier with the Access2000 process).

Thanks!

Nicole

[deleted]

A hierachical structure only has parents and children, never 'levels'.

You start with one or more top-level categories. They each have any number of children, who have any number of children etc etc.

This is also the only way to get the entire structure: lookup the top level (the only level that does not have a parent-level)
Then lookup all the categories that have the top-level category as a parent.
Then lookup all the categories who have those categories as parents etc etc.

It's a recursive process.

This article explains a related databas design:
http://www.hvt-automation.nl/yapf/index.php?cmd=viewitem&itemid=4

Anon

From your article, it looks like I designed my table correctly. The CategoryLevels I had in there was mostly for my own benefit, so visually I could see what was what.

I'm still a little confused as to how to query the db to report all levels... do you think you could be a little more specific? If I need to report the structure for ONE product, don't I need to work backwards, from the child category?

Thanks,

Nicole

Anon

One more question.

Can you tell me what the SQL statements would look like do even run a query like that? I gathered by your article that I'm going to have to run more than one query. So to output all levels, I'm thinking that I'm going to have a query that is built on a query that is built on a query, etc.

That's where I get confused! :-)

[deleted]

The entire structure is based on parents and children.

Parent's don't know who their children are, but children know who their parents are.

So, if you want to see the entire tree you have to work from the highest parent to the lowest child.

Some databases like Oracle have special queries that can handle these things, but in MySQL there aren't.

In MySQL you'll have to run a seperate query for each parent to find it's children.

The confusing part is the recursiveness.
btw: this is a bit of a dangerous toy, so double check the code before you run it, or build in a failsafe that will force the whole thing to stop after X queries.

The principle is that make a function that takes just one record-id, that of the parent for which you want to find the children.

This function should run the query, fetch the results, and for each child it finds, it must call itself to find the children of that child.

There examples of this recursive principle all over the place, it is often used to read directory-trees, which is basically the same principle, a dir has subdirs who have subdirs.

If you still need more I'll see if I can write you up something.

Anon

Ok, just to be a TOTAL pain in the butt, can you write me an example?

I understand that parents don't know who their children are (those irresponsible parents) but children know their parents. But the code to "call_itself" to find children of that child is beyond me.

Its funny that it is such a widely used format but it is so difficult to understand.

And btw, I have no excuses. It's not Monday, I DID drink my coffee this morning, and I didn't party last night. I'm just not very good at the query side of all this!

Thanks for your input on my other post too.

Nicole

spxdcz

This may be slightly confusing for a beginner, but the best solution I have seen (and I have looked for many years...) is the one I found at:

'Genealogical Representation of Trees in Databases', by Miguel Sofer http://www.utdt.edu/~mig/sql-trees

This method involves having the 'application' (maybe vbscript in access, or php for a mysql backend) create an 'id' structure that represents the tree hierarchy. From a previous document I wrote:

An example of the categoryId structure might be:

00a
00a001
00a001001

The 'id' of a category is made up from a multiple of set-width of characters, depending on the application using the database – a 3-character width is a good start.

This id represents the 'number' of the category, but, to save resources, encoded to higher than base 10, e.g. base 32 (the highest available through a particular PHP function). So, each 'node' of category has 3 characters, which represents a number encoded in base32: i.e. three characters can represent numbers up to:

 32*32*32 = 32,768

This infers that each 'node' can have over 32,000 categories. These three characters (the 'id') are then appended onto the 'id' of the parent category. Thus, the maximum 'depth' of the tree will be the maximum size of the database id field divided by the number of characters:

 For a MySQL VARCHAR field: 255/3 = 85

This means that the tree can have 85 levels (a 'depth' of 85), each containing 32,000 nodes.

The childCount field is used to store the actual 'number' of a nodes highest child id, so that if a new child is added to a node, simply increment this field, encode as base 32, and append to the parent id to get the new child id.

This method of storing hierarchical structures allows us to perform usually complex queries with little processing power:

The depth of any node can be calculated simply by dividing the number of characters in the id (e.g. 3, 6, 9, etc.) by the number of characters used to represent each node (e.g. 3).
A sub-node tree can be found by selecting categories with 'id like '00100a%', where 00100a is an example of the current category.
The descendants of the node (i.e. those from the node up to root) can be found easily be simply recursively removing the last three characters from the id.

Sorry, that's all a bit in-depth - read the paper at the above link for a good analysis.

[deleted]

So basically each node's ID is made up of the ID's of all it's parents and grandparents.

It's a method I guess, exchanging redundant data against multiple queries.

I'm not quire sure how one would go about printing an entire tree using this method. I imagine it would involve a sh*tload of substring operations queries.

Also I shudder to think about how one would move a part of a tree from one parent to another.

spxdcz

Printing an entire tree is very easy in one select - you just "select * from table where id like '001%' order by id". (just make the 001 the id of the 'top' of the tree, or even just '%' to get the whole tree)

But you're absolutely correct about moving the structure of the tree. And of course, if you're using the id field to map other objects to the hierarchy, you're in even worse trouble...