MySQL Nested Sets: Using data from other tables

If you don't already know what "Nested-Sets" are, check out this article about them. Basically, it is a way of storing hierarchical data in SQL that allows you to retrieve an entire tree in one query with limited joins, as opposed to the recursive joins of the "Adjacency List" method common to programmers.

Anyhow, the SQLDev team article gives the following query as a method to fetch a tree from a node:

SELECT node.name, (COUNT(parent.name) - sub_tree.depth) AS depth
FROM nested_category AS node,
nested_category AS parent,
nested_category AS sub_parent,
(
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'PORTABLE ELECTRONICS'
GROUP BY node.name
ORDER BY node.lft
)AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.lft;

I wanted to one up this. My table looks a little different from the SQL Dev team's. Here's the general layout:

Table categories:
cid l category r
0 0 Departments 11
1 1 House 6
2 2 Kitchen 5
3 3 Plates 4
4 7 Garden 10
5 8 Hoses 9

"Departments" is our "root" with two branches: "House" and "Garden". Kitchen is a sub-category of House, and Plates is a sub-category of Kitchen. "Hoses" is the only sub-category of "Garden". I added a "CID" field so that I would have a permanent unique identifier for each category, even if I chose to change the name. I then also have a category_links table:

Table category_links
clid cid pid
0 3 1
1 3 2
2 3 3
3 3 4

Imagine we have a products table with an index called "pid". We don't actually need to know what the rest of the table looks like, but this set-up allows each category to be linked to several products, and vice-versa. Now, what I want to do is show the tree, starting from a node, as in the earlier query. But I also ONLY want to show categories that have products attached to them. Actually -- because my main script shows products associated with a categories sub-categories as well as it's own products, we need to list any category that has products associated with it OR that has sub-categories with products.

As you can see in the category_links table, the only category with products attached, for this example, is "Plates". So we want to show the tree, with depth, starting at "Departments" (we could start lower down the tree if we wanted), but we want to hide categories have no products and no sub-categories with products. The desired result is:

Departments
House
Kitchen
Plates

Keep in mind that this will work on much more complex trees, but for the sake of this example, I am using a rather simple tree as an example. For instance, "Kitchen" could have more subcategories at the same level as plates, and assuming they had no products associated with them, they would not show up.

Now, as in the above query, we cannot limit or join onto our main table, because that would through of the COUNT() function we are using to determine depth. We need yet another inner-query to be joined as a table. Here is my query:

SELECT node.cid, node.category, node.l, node.r, (COUNT(parent.cid) - subtree.depth) AS depth
FROM categories AS node, categories AS parent, categories AS sub_parent, categories as sub_parent2,
( SELECT node.cid, COUNT(parent.cid) AS depth
FROM categories AS node, categories AS parent
WHERE node.l BETWEEN parent.l AND parent.r AND node.cid = '$department_id' GROUP BY node.cid ORDER BY node.l )
AS sub_tree,
(SELECT c.cid FROM categories AS c, category_links AS cl WHERE cl.cid = c.cid GROUP BY c.cid)
AS sub_tree2
WHERE node.l BETWEEN parent.l AND parent.r
AND node.l BETWEEN sub_parent.l AND sub_parent.r
AND sub_parent.cid = sub_tree.cid
AND sub_parent2.cid = sub_tree2.cid
AND sub_parent2.l BETWEEN node.l AND node.r
GROUP BY node.cid ORDER BY node.l

'$department_id' is a php variable that could be set to any CID value, which would start reading the tree from that node, as in the example above. But we've added two more tables (sub_tree2 and sub_parent2) in order to limit our results to categories with products or with sub-categories with products.