Unlimited Category Structure

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
peterguest
Forum Newbie
Posts: 1
Joined: Sun Feb 08, 2009 11:23 am
Location: South Africa

Unlimited Category Structure

Post 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
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Unlimited Category Structure

Post by Christopher »

See this recent discussion:

viewtopic.php?f=19&t=93263
(#10850)
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Unlimited Category Structure

Post 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.
User avatar
allspiritseve
DevNet Resident
Posts: 1174
Joined: Thu Mar 06, 2008 8:23 am
Location: Ann Arbor, MI (USA)

Re: Unlimited Category Structure

Post 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.
User avatar
inghamn
Forum Contributor
Posts: 174
Joined: Mon Apr 16, 2007 10:33 am
Location: Bloomington, IN, USA

Re: Unlimited Category Structure

Post 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)
);
 
User avatar
allspiritseve
DevNet Resident
Posts: 1174
Joined: Thu Mar 06, 2008 8:23 am
Location: Ann Arbor, MI (USA)

Re: Unlimited Category Structure

Post 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
User avatar
inghamn
Forum Contributor
Posts: 174
Joined: Mon Apr 16, 2007 10:33 am
Location: Bloomington, IN, USA

Re: Unlimited Category Structure

Post 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)
);
 
User avatar
allspiritseve
DevNet Resident
Posts: 1174
Joined: Thu Mar 06, 2008 8:23 am
Location: Ann Arbor, MI (USA)

Re: Unlimited Category Structure

Post 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.
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Unlimited Category Structure

Post 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? :D 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.
User avatar
allspiritseve
DevNet Resident
Posts: 1174
Joined: Thu Mar 06, 2008 8:23 am
Location: Ann Arbor, MI (USA)

Re: Unlimited Category Structure

Post by allspiritseve »

josh wrote:I may end up using a hybrid approach after all though.
Wow, he's coming over to the dark side!
Post Reply