4

I'd like to be able to build the breadcrumbs for a content page, however the categories a piece of content is in can have unlimited depth, so i'm not sure how to go about it without getting each category one by one and then getting its parent etc. It seems like it could be a simpler way but I can't figure it out.

I have an articles table

article_id
article_name
article_cat_id

I also have a categories table

cat_id
cat_name
cat_parent

Cat parent is the id of another category of which a category is a child.

Imagine an article which is 5 categories deep, as far as I can tell i'd have to build the breadcrumbs something like this (example code obviously inputs should be escaped etc)

<?php
$breadcrumbs = array(
    'Category 5',
    'Content Item'
);
$cat_parent = 4;

while($cat_parent != 0) {
    $query = mysql_query('SELECT * FROM categories WHERE cat_id = '.$cat_parent);
    $result = mysql_fetch_array($query, MYSQL_ASSOC);
    array_unshift($breadcrumbs, $result['cat_name']);
    $cat_parent = $result['cat_parent'];
}
?>

This would then give me

array(
'Category 1',
'Category 2',
'Category 3',
'Category 4',
'Category 5',
'Content Item'
)

Which I can use for my breadcrumbs, however its taken me 5 queries to do it, which isn't really preferable.

Can anyone suggest any better solutions?

John Mellor
  • 2,351
  • 8
  • 45
  • 79
  • 2
    Unless you want to use some complicated data structures in your DB, or switch to a database that supports recursive queries, your method is the simplest option. – Marc B Apr 05 '11 at 20:54
  • 1
    What Marc B said. Add some caching (ie check if you've calculated the parent tree for that article recently) and you're set. – Fanis Hatzidakis Apr 05 '11 at 21:07

2 Answers2

3

Here are some easy options in order of simplicity:

  1. Stick with the design you have, use the recursive/iterative approach and enjoy the benefits of having simple code. Really, this will take you pretty far. As a bonus, it is easier to move from here to something more performant, than from a more complicated setup.

  2. If the nr of categories isn't very large, you can select all of them and build the hierarchy in PHP. Due to pagesize the amount of work required to fetch 1 rows vs a whole bunch of them (say a few hundred) is pretty much the same. This minimizes the nr of queries/network trips, but increases the amount of data transported over the cable. Measure!

  3. Cache the hierarchy and reload it entirely every X unit of time or whenever categories are added/modified/deleted. In it's simplest form, the cache could be a PHP file with a nested variable structure containing the entire category hierarchy, along with a simple index for the nodes.

  4. Create an additional table in which you have flattened the hierarchy in some way, either using nested sets, path enumeration, closure table etc. The table will be maintained using triggers on the category table.

I would go for (1) unless you are fairly certain that you will have a sustained load of several users per second in the near future. (1 user per second makes 2,5 million visits a month).

There is nothing wrong with simple code. Complicating code for a speedup that isn't noticable is wrong.

Ronnis
  • 12,593
  • 2
  • 32
  • 52
  • We're currently at 2 million pageviews a month and 5 million on heavy months, that's why i'm looking to optimise :) I'm not sure 2 or 3 would really work as the number of categories is going to be pretty high, although considering the number of page loads, perhaps caching to APC (which we use) may be worthwhile. 4 seems like it could work if (using the simplified example in the first post) I created an article_hierarchy of some sort with 5,4,3,2,1 inside. But that would be difficult to update if I say moved a category, compared to simply creating the article in the first place – John Mellor Apr 05 '11 at 23:05
  • @Freeze, surely the category hierarchy (excluding the products) remains unchanged for longer periods of time? To create the breadcrumb, you would select only from products table by PK and then traverse the categories from your cache. Roughly how many categories and products do you have? – Ronnis Apr 06 '11 at 07:53
  • 128 categories with 58,560 articles at the moment the deepest category we have is 5 (although it could go deeper). I'm working on a solution based on some info in the links from @mfonda although i'm constrained by my admin interface at present, so i'm waiting till i've got a clear solution before posting an edit. – John Mellor Apr 06 '11 at 14:05
  • 1
    @Freeze, ok with only 128 categories, you can store it as an array and cache it in APC or a file. So, pick the article_id from URL, perform the lookup in product table and use the cat_id to traverse the category structure in PHP. Either you expire the cache every X seconds/minutes or you overwrite it whenever a category is added/deleted/moved. – Ronnis Apr 06 '11 at 18:49
  • Accepted answer, sorry for taking so long I wanted to put things to the test a little before accepting – John Mellor Apr 09 '11 at 14:23
2

There are two commonly used methods of handling hierarchal data in relational databases: the adjacency list model and nested set model. Your schema here is currently following the adjacency list model. Check out this page for some example queries. See also this question here on SO with a lot of good information.

Community
  • 1
  • 1
mfonda
  • 7,873
  • 1
  • 26
  • 30