Page 1 of 1
Unlimited Category Structure
Posted: Sun Feb 08, 2009 11:35 am
by peterguest
Hi,
I have tried for a couple of days now to build a page that displays an unlimited category structure. Currently my categories table in mysql has the following fields. category_id, parent_id, category_title,category_desc.
How do I iterate through the categories to get the structure back. Remember the categories can have UNLIMITED sub-categories e.g.
Root 1
-Sub1
--Sub-Sub1
-Sub2
--Sub-Sub1
--Sub-Sub2
---Sub-Sub2-Sub1
-Sub3
I think I need a recursive function or something. I am not sure on the theory of it? Can anyone assist me with this. I have had a look a many article but nothing really helped me.
Thanks in advance
Peter
Re: Unlimited Category Structure
Posted: Sun Feb 08, 2009 12:15 pm
by Christopher
See this recent discussion:
viewtopic.php?f=19&t=93263
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 2:04 am
by josh
You're implementing adjacency list which requires recursion, unless you create a hybrid of materialized path. THere's also nested set which is considered the holy grail.
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 8:44 am
by allspiritseve
josh wrote:THere's also nested set which is considered the holy grail.
...until you want to select all immediate children

then it gets a little clunky compared to adjacency list.
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 2:06 pm
by inghamn
allspiritsteve wrote:
...until you want to select all immediate children

then it gets a little clunky compared to adjacency list.
Not necessarily so. Nested set is really a two-table setup. You have the categoryIndex with the lft and rgt values, but you still have the main category table. In the main category table, you can still have parent_id as a field. Then you get the best of both worlds. Use the main table with the parent_id for direct children, if you like. And select against the index for the hard stuff (ancestors, descendents, depth, etc.)
Code: Select all
CREATE TABLE categories (
id int UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
name varchar(255) NOT NULL,
parent_id int UNSIGNED NOT NULL,
FOREIGN KEY (parent_id) REFERENCES categories(id)
);
CREATE TABLE categoryIndex (
category_id int UNSIGNED NOT NULL,
lft int UNSIGNED,
rgt int UNSIGNED,
FOREIGN KEY (category_id) REFERENCES categories(id)
);
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 2:25 pm
by allspiritseve
inghamn wrote:Not necessarily so. Nested set is really a two-table setup. You have the categoryIndex with the lft and rgt values, but you still have the main category table. In the main category table, you can still have parent_id as a field. Then you get the best of both worlds. Use the main table with the parent_id for direct children, if you like. And select against the index for the hard stuff (ancestors, descendents, depth, etc.)
Actually I experimented with something similar in a different thread, except I moved the parent_ids out into another table. Josh didn't like it though... he considered it to be a breach of normalization. Feel free to check out the thread here:
viewtopic.php?f=19&t=88277
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 2:35 pm
by inghamn
In some of my applications, I do have a seperate table for the parent_ids. But that's only when I want to support a Directed Acyclic Graph, instead of just a tree. In our content manager, content goes into sections of the site, and sections can have multiple parents. Which is to say each section lives in multiple places at once!
The joy of it is that you can have your cake, and eat it, too. The Nested Set algorithm supports graphs as well as trees. The downside to doing graphs is that for moving nodes or inserting nodes, you absolutely must do a recursive depth-first traversal to create the index. The shortcuts I've seen where people increment the lft and rgt values to handle inserts only work if you have an actual tree.
I came to this design after reading someone's brilliant paper on the subject:
http://www.informatik.hu-berlin.de/Fors ... logies.pdf
So our full table structure is
Code: Select all
CREATE TABLE categories (
id int UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
name varchar(255) NOT NULL,
);
CREATE TABLE category_parents (
category_id int UNSIGNED NOT NULL,
parent_id int UNSIGNED NOT NULL,
PRIMARY KEY (category_id,parent_id),
FOREIGN KEY (category_id) REFERENCES categories(id),
FOREIGN KEY (parent_id) REFERENCES categories(id)
);
CREATE TABLE categoryIndex (
category_id int UNSIGNED NOT NULL,
lft int UNSIGNED,
rgt int UNSIGNED,
FOREIGN KEY (category_id) REFERENCES categories(id)
);
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 2:40 pm
by allspiritseve
inghamn wrote:In some of my applications, I do have a seperate table for the parent_ids. But that's only when I want to support a Directed Acyclic Graph, instead of just a tree. In our content manager, content goes into sections of the site, and sections can have multiple parents. Which is to say each section lives in multiple places at once!
Right... I need to give certain items multiple parents, so having that extra table is a necessity, but it doesn't change the overall system. Glad to know others feel the same way I do, and I'll have to check out that article.
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 7:38 pm
by josh
allspiritseve wrote:inghamn wrote:Not necessarily so. Nested set is really a two-table setup. You have the categoryIndex with the lft and rgt values, but you still have the main category table. In the main category table, you can still have parent_id as a field. Then you get the best of both worlds. Use the main table with the parent_id for direct children, if you like. And select against the index for the hard stuff (ancestors, descendents, depth, etc.)
Actually I experimented with something similar in a different thread, except I moved the parent_ids out into another table. Josh didn't like it though... he considered it to be a breach of normalization. Feel free to check out the thread here:
viewtopic.php?f=19&t=88277
Nested set is not about 2 tables. and breach of normalization doesn't mean I didn't like it

Materialized path lets you grab all descendants or children in one pass, I don't see that as an advantage over nested set tho since that is just one operation I would want to do. What about finding depths or ancestors? If a node is 5,000 nodes deep in the tree should I have to issue 5,000 queries to find that out?

The only down side to having a hybrid is a developer might come along and write code to do it the hard way. You also make your database less safe. As is nested set is more susceptible to corruption. If you're going to take that 1 step the next step would be to go all the way to an object database. I may end up using a hybrid approach after all though. Or at least using a database view.
Re: Unlimited Category Structure
Posted: Mon Feb 09, 2009 7:44 pm
by allspiritseve
josh wrote:I may end up using a hybrid approach after all though.
Wow, he's coming over to the dark side!