Generate breadcrumbs of categories stored in MySQL

Question

In MySQL, I store categories this way:

categories: - category_id - category_name - parent_category_id

What would be the most efficient way to generate the trail / breadcrumb for a given category_id?

For example breadcrumbs(category_id): General > Sub 1 > Sub 2

There could be in theories unlimited levels. I'm using php.

UPDATE: I saw this article (http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/) about the Nested Set Model. It looks interesting, but how would you ago about dynamically managing categories? It looks easier on paper, like when you know ahead of times the categories, but not when the user can create/delete/edit categories on the fly ... What do you think?

Answer 1

I like to use the Materialized Path method, since it essentially contains your breadcrumb trail, and makes it easy to do things like select all descendants of a node without using recursive queries.

Materialized Path model

The idea with the Materialized path model is to link each node in the hierarchy with its position in the tree. This is done with a concatenated list of all the nodes ancestors. This list is usually stored in a delimited string. Note the “Linage” field below. CAT_ID NAME CAT_PARENT Lineage 1 Home . 2 product 1 .1 3 CD’s 2 .1.2 4 LP’s 2 .1.2 5 Artists 1 .1 6 Genre 5 .1. 5 7 R&B 6 .1. 5.6 8 Rock 6 .1. 5.6 9 About Us 1 .1

Traversing the table

Select lpad('-',length(t1.lineage))||t1.name listing
From category t1, category t2
Where t1.lineage like t2.lineage ||'%'
    And t2.name = 'Home';
Order by t1.lineage;

Listing

Home
-product
–CD’s
–LP’s
-Artists
–Genre
—R&B
—Rock
-About Us