Building Breadcrumbs in MySQL

Question

I have a table that defines the possible categories in my website - fields look something like this:

  - id
  - name
  - parentID

The information is stored something like this:

+-----+------+----------+
| id  | name | parentID |
+-----+------+----------+
|  1  | pets |        0 |
+-----+------+----------+
|  2  | cats |        1 |
+-----+------+----------+
|  3  | dogs |        1 |
+-----+------+----------+

A parentID of 0 indicates that the category/page is on the home level. I'm looking for a way to quickly and easily generate the parent categories.

The first method that came to mind was a series of SQL queries, but I quickly realised that this would be insidiously resource intensive the more complicated the site got.

Reading through the mysql manual, I've seen that mysql can use loops and conditional statements, however I'm unsure how I'd put those into practice here.

Ideally, I'd like to have a single query that pulls up all directly related parent elements.

If I were looking at the Pets category, I would only see home because it's on the top level. As soon as I drill down (either into cats, dogs or a page under pets) then I should see pets on the bar - the same goes for subsequent child categories and pages.

What's the most efficient way to generate a list of categories using information stored in this fashion? If this question requires more clarification, please ask, and I will do my best to provide more information.

Clarification: This is part of a CMS - and as such, users are going to need the ability to make changes to categories on the fly. I've looked at several data storage schemes (such as nested sets) and they do not appear to lend themselves well to a simple form for making changes to navigation.

As such, any method needs to be easily a) understood by a user, and b) implemented easily to a user.

The categories are best described as folders on a PC, rather than tags. When you view any given category, you can see the immediate children of that category, as well as immediate child pages.

When you view a category or a page, the parent categories (but not itself are visible).

Example: I have German Shepard which resides under dogs which is under pets

When viewing *pets*:           Home
When viewing *dogs*:           Home -> Pets
When viewing *German Shepard*: Home -> Pets -> Dogs

Answer 1

Consider using "nested sets" model instead: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Update (based on clarification to the question): Nested sets model does not have to be (in fact I have a pretty hard time imagining why would it be) exposed to end users. All directory-style operations (adding a new folder / subfolder; moving folder to a different path, etc...) can be supported in nested sets model, though some are a bit harder to implement then others. Article I've linked to provides examples for both adding and deleting of (sub)folder.

Answer 2

Could you have a stack or ordered set (ordered by how the user applied filters to their browsing) containing your breadcrumb, stored on the session?

I could see it getting grim when you started cross-querying, but sometimes data isn't hierarchical, but more of a soup of tags, and the above starts being your tag-soup clarification breadcrumb.

Most websites don't actually feature good (or any) tag soup drilling down. E.g., how many times have you been look at the sale CDs on a website, and wanted to drill down to just see the Metal CDs (for example), but clicking on the "Rock and Metal" link on the left took out to the top level metal category, instead of acting as a filter on your current browsing state.

So - is your problem actually a tag soup that you're applying a false hierarchy onto? Should you in fact be looking at automatic tag generation libraries that you can pass your items into, and tag lookup mechanisms? Okay, I'm sure your personal website won't be complex enough to ever require tag search, but in general terms, I think it is worth thinking about.