SitePoint Sponsor

User Tag List

Results 1 to 12 of 12
  1. #1
    SitePoint Guru
    Join Date
    Dec 2005
    Posts
    982
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Searching Infinite Sub Categories

    For the longest time I've been working with a categorization system that only allows for 1 level of nesting (parent -> child_1), but now I have a requirement to add more. I can easily allow for an arbitrary number while knowing that the more levels of categories I add, the longer and more complex the SQL will be from extra joins, but I want to know if anyone has figured out a way to do infinite levels of nesting (parent -> child_1 -> child_2 [ -> child_n ]).

    I can't fathom a way to do this (there are no loops or recursive functions in MySQL that I am aware of), but I thought I would ask before programming an arbitrary restriction into the system.
    MySQL v5.1.58
    PHP v5.3.6

  2. #2
    reads the ********* Crier silver trophybronze trophy longneck's Avatar
    Join Date
    Feb 2004
    Location
    Tampa, FL (US)
    Posts
    9,854
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    Check out our new Industry News forum!
    Keep up-to-date with the latest SP news in the Community Crier

    I edit the SitePoint Podcast

  3. #3
    SitePoint Guru
    Join Date
    Dec 2005
    Posts
    982
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Wow that's cool. Not the database schema I'm used to, but it looks really effective! I'll have to play around with it (specifically the rebuilding of the tree) before I make my mind up about it, but I can tell some guy thought long and hard about this problem once before
    MySQL v5.1.58
    PHP v5.3.6

  4. #4
    reads the ********* Crier silver trophybronze trophy longneck's Avatar
    Join Date
    Feb 2004
    Location
    Tampa, FL (US)
    Posts
    9,854
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    just so you know, inserting a leaf node is really easy. use left and right values that are +2 of the sibling to its left, and add 2 to the left and right values of all of the nodes with a left value larger than that same sibling.
    Check out our new Industry News forum!
    Keep up-to-date with the latest SP news in the Community Crier

    I edit the SitePoint Podcast

  5. #5
    SitePoint Guru
    Join Date
    Dec 2005
    Posts
    982
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yeah, I saw that on page 3. I just want to play around with other irregularities of our category models. For instance, we have multiple trees. We have the main category tree that the users navigate through, but we also have internal categories. These are used for special groupings that aren't in the normal structure of site (such as sales and holiday gift guides). I haven't had a chance to play with it all yet, but I think I can include a "tree" column (where only 1 is public or something).

    Looks like it'll be fun
    MySQL v5.1.58
    PHP v5.3.6

  6. #6
    SitePoint Addict
    Join Date
    Mar 2005
    Posts
    314
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    While that article might be informative, it's plain complicated.

    Do a search on google for a recursive category function. That's what you're after. 1 function to loop (and continue to loop through all nodes) until the last category is shown.

    You'll need three main fields in your category table:

    cid, parentid and level.

    Level is good for when you make a pulldown menu and you want your pulldown values to look like:

    Cat 1
    --- Cat 2
    ------ Cat 3
    Cat 4
    Cat 5
    --- Cat 6

    As you can see, if you have that "level" in your db schema you'll be able to work with your "spacing" if you are writing pulldown menus as well.

    From that category function I'm mentioning you'll be able to do a lot. You'll be able to generate single column views, double, tripple and 4-column views similar to ebay and their layout.

    I guess it's just a matter of preference. Last year when I was looking around for nested category support in PHP I saw that article above. I wanted something fast, that didn't require too much thought at the time. This was complicated for me back then and I find my solution on google.

    Search "nested category" or "PHP nested category function recursive". You'll find some great articles from PHPBuilder and other sites focusing on a more simplier approach to your problem

    Peter

  7. #7
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,215
    Mentioned
    58 Post(s)
    Tagged
    3 Thread(s)
    peter, you consider a query within a loop within a loop within a loop ad nauseam to be fast???

    brandon, you really do not want an "infinite" number of levels

    in the real world, there will be some maximum number of levels, and even if this number seems large, it will not be infinite

    think of your users, drilling down through those levels

    at what point will a user say "da heck wid dis, i'm outta here" and go somewhere else?

    have a look at this article: Categories and SUbcategories

    even if you decide to have 15 levels (and i can assure you, that's still too many from a usability point of view), the sql is still very fast
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  8. #8
    SitePoint Guru
    Join Date
    Dec 2005
    Posts
    982
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I saw that post, and that's basically what I do with my categories now and its a schema that I am very familiar with. It works well and is easy to be understood by other developers that may edit my code.

    That being said, I am looking at this new article with an open mind because it is very intriguing to me. I've never seen anything like it so I really just want to play with it and understand it. The biggest benefit I see from it is not speed (which is probably negligible from what you say in your article) or the ability to have infinite levels (like you said, that's way too many for what I'm going to use it for), but it is maintenance free (kinda). If I choose an arbitrary number, say 5, and build the site around that number, I know one day we'll push it to 6. If we change it to 6, I have to update SQL in a couple different spots and then edit my server side code to handle the extra fields returned too. Its not a show stopper, but maintenance free code is kinda nice.

    On the other hand, it is much more complex to explain (I couldn't do it without a diagram), and the upkeep on the server is much more involved. Changing a node around can affect every node in the tree and require a couple hundred row changes. I still want to get some time to play with it today before deciding on anything, and I still welcome more input from the pros here.
    MySQL v5.1.58
    PHP v5.3.6

  9. #9
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,215
    Mentioned
    58 Post(s)
    Tagged
    3 Thread(s)
    see Joe Celko's Trees and Hierarchies isbn 1-55860-920-2
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  10. #10
    SitePoint Guru
    Join Date
    Dec 2005
    Posts
    982
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I just got done reading his post on searchoracle.com and was thinking about looking for SQL for Smarties. I read that he devotes a couple chapters to hierarchal data storage. Do you recommend one over the other?
    MySQL v5.1.58
    PHP v5.3.6

  11. #11
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,215
    Mentioned
    58 Post(s)
    Tagged
    3 Thread(s)
    yes, SQL For Smarties is the better choice, simply because there's so much more in it besides trees and hierarchies -- the chapter on nested sets is sufficiently comprehensive to let you know if you really want to use this data model
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  12. #12
    SitePoint Guru
    Join Date
    Dec 2005
    Posts
    982
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thank you as always, Rudy and longneck (sorry, I don't know your first name).
    MySQL v5.1.58
    PHP v5.3.6


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •