Re: Creating a Hierarchical Structure

> How would you, or what is the commonly accepted way, of creating a database
> which represents a hierarchical category structure ala Yahoo!?
>

> What I have done until now is to create a table called categories. Each
> field has a categoryID, a parentID and the category's name. The parentID is

This works if every category has a single parent. However if a category can have more than one parent (as in most web directories), you need a more generalized representation. A typical implementation would be as follows:

create table node( node_id int primary key,...) create table node_relationship( parent_node_id int references node, child_node_id int references node,
primary key (parent_node_id, child_node_id))

This structure can represent any directed graph structure, so some problems can arise if someone creates a loop.

A few other notes:

1. The "nested set" approach doesn't work on this type of graph without a lot of modification.
2. Storing the transitive closure of the category structure is not prohibitive. The average depth of a category is around 10, so the TC will have about that number of entries for each category. The entries themselves are just pairs of integers, 8 bytes or so. TC's are also handy for detecting loops.
3. Either of the above approaches can be a pain to keep updated.
4. We need an FAQ to get all these points straightened out.

> I was talking to some guy yesterday who said the standard what of creating
> such a system in a directory was to have a table which contains your root
> categories and then a new table for every level of sub-category. So if your
> directory goes 10 levels deep you have 10 category tables each containing
> the categories of a level.
>

Huh? Received on Wed Aug 29 2001 - 16:16:39 CDT