how to best implement dynamic sub-categories

[old_iron]

Hi all,

How do you all implement dynamic sub-categories of items, e.g. products in a shop?

For example you may have an item belonging in:
computer -> software -> games -> shoot em up (1)
or
computer -> misc (2)

Example (1) is in a 'third-level' subcategory whereas item (2) is just at a 'first-level'. How can these be implemented in a database where you may have variable sub-category depths?

Obviously a variable amount of tables (sub-category, sub-sub-category, sub-sub-sub-category) is inefficient.

So what I thought of doing was just having one table: categories

ID - name
----------
1 - computer
2 - software
3 - misc
4 - games
5 - shoot em up

And then having another table showing the relationships between categories:

CREATE TABLE category_relationships (
   cat_id int NOT NULL,
   sub_id int NOT NULL
)

Where both id's would be foreign keys to the 'categories' table defining which is a sub-category of a given category (or sub-category) i.e. one such record might be:

Array(
   [cat_id] => 4
   [sub_id] => 5
)

Showing that 'shoot em up' is a sub-category of 'games'.

Then the product table would have a foreign key to whichever category or sub-category that product belonged to.

My problem is how to get the 'tree' of categories, i.e. if I know a product belongs in the 'shoot em up' category, how do I recursively fetch each preceeding sub-category?

I.e. how would I write a query which would fetch all the categories in between up to the root category: games, software, computer.

Obviously I could make a simple recursive function server-side to fetch the previous category until there were no more categories (we'd reached the 'root') but this involves multiple queries. Is there anyway to do this in less queries, or more efficiently? With this table structure, or any other!

Any help is apprecated!

[guido2004]

If each subcategory can only relate to one 'higher' category, then the second table is superfluous. A parentid field in the categories table is enough.
As far as creating the tree is concerned, there are already lots of posts about that. Try a search. There's also a word for that type of query, r937 posts it all the time, but I don't remember

[r937]

the parent_id design is called the adjacency data model

more information here: Categories and Subcategories

[guido2004]

the parent_id design is called the adjacency data model

See
Now if I could only remember that word...

[old_iron]

First, thank you both for your help!

Rudy, that article was very informative, great work, but I have a question: you say that if the hierarchy is fifteen levels deep, we'd have to code a query with fifteen self-joins - that suggests to me the number of levels is somehow predetermined. What if I was creating a database for an online shop and allowed the user to determine the categories/subcategories (i.e. by creating a new node and specifying its parent node) - this way the depth could be infinite.

Would it be better to limit the hierarchy depth in advance? Or should we generate the query in a server-side language each side a new level is created? (or for that matter, deleted) By this I'd mean that if a user entered a new category which created a new level, the system would find the stored SQL and alter it to include a further self-join.

[old_iron]

See
Now if I could only remember that word...

well, I hadn't heard of it before now so that's one up on me!

[r937]

as i said in that article, if you have a hierarchy that is 15 levels deep, you may want to reconsider whether it's really user-friendly

me, if i have to drill down through 15 levels in order to find what i'm looking for, i'm outta there long ago

so, yeah, use your app to limit the number of levels -- do it for your users!!

[old_iron]

okay, thanks Rudy!