Unlimited Category Structure
Moderator: General Moderators
-
peterguest
- Forum Newbie
- Posts: 1
- Joined: Sun Feb 08, 2009 11:23 am
- Location: South Africa
Unlimited Category Structure
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
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
- Christopher
- Site Administrator
- Posts: 13596
- Joined: Wed Aug 25, 2004 7:54 pm
- Location: New York, NY, US
Re: Unlimited Category Structure
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.
- allspiritseve
- DevNet Resident
- Posts: 1174
- Joined: Thu Mar 06, 2008 8:23 am
- Location: Ann Arbor, MI (USA)
Re: Unlimited Category Structure
...until you want to select all immediate childrenjosh wrote:THere's also nested set which is considered the holy grail.
- inghamn
- Forum Contributor
- Posts: 174
- Joined: Mon Apr 16, 2007 10:33 am
- Location: Bloomington, IN, USA
Re: Unlimited Category Structure
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.)allspiritsteve wrote: ...until you want to select all immediate childrenthen it gets a little clunky compared to adjacency list.
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)
);
- allspiritseve
- DevNet Resident
- Posts: 1174
- Joined: Thu Mar 06, 2008 8:23 am
- Location: Ann Arbor, MI (USA)
Re: Unlimited Category Structure
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=88277inghamn 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.)
- inghamn
- Forum Contributor
- Posts: 174
- Joined: Mon Apr 16, 2007 10:33 am
- Location: Bloomington, IN, USA
Re: Unlimited Category Structure
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
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)
);
- allspiritseve
- DevNet Resident
- Posts: 1174
- Joined: Thu Mar 06, 2008 8:23 am
- Location: Ann Arbor, MI (USA)
Re: Unlimited Category Structure
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.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!
Re: Unlimited Category Structure
Nested set is not about 2 tables. and breach of normalization doesn't mean I didn't like itallspiritseve wrote: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=88277inghamn 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.)
- allspiritseve
- DevNet Resident
- Posts: 1174
- Joined: Thu Mar 06, 2008 8:23 am
- Location: Ann Arbor, MI (USA)
Re: Unlimited Category Structure
Wow, he's coming over to the dark side!josh wrote:I may end up using a hybrid approach after all though.