Finding all non-empty categories in a tree

Question

I have a categories table set up as so [id, name, parent_id] and a items table [id, name, category_id, visible]. What I'm trying to do is create a query that will return all the ids of all non-empty categories, non empty being that it or one of it's children has at least one item belonging to it. What would be the best way to do this in MySQL?

edit

SELECT DISTINCT category_id FROM Items

This works for categories containing items, but I also need the parent categories of all item containing categories. This query will be used as a subquery along with some other filters.

Top Level Category

->Second Level Category

-->Third Level Category

--->Item 1

--->Item 2

Answer 1

All non-empty categories, and only those, have items with category_id pointing at them, therefore you could just select category_ids from items table:

SELECT DISTINCT category_id FROM Items

As far as I know, you can't select all the ancestors of these categories in one query, however you might want to use another tree model.

With the nested set model, your query could look like this:

SELECT DISTINCT c.id FROM Categories c JOIN Items ON c.id = category_id JOIN Categories ancestors ON c.lft BETWEEN ancestors.lft AND ancestors.rgt

I'm not sure if it'll work, but you can try.

Answer 2

Maybe off topic, but I think it is still worth referencing: Extensive Article on Managing Hierarchical Data in MySQL.