Getting consistent menu tree data from menu tables in MySQL

Question

Hi everybody, I have a tree / ancestor / query problem I'm not able to solve:

I have a table holding menu data and a table containing all the ancestors of the menu:

table menu               table ancestors
+-----+------------+--------+     +---------+--------------+-------+
| id  |      title | active |     | menu_id |  ancestor_id | level |
+-----+------------+--------+     +---------+--------------+-------+
|   1 |       Home |      0 |     |       1 |            0 |     0 |
|   2 |       News |      0 |     |       2 |            1 |     1 |
|   3 |        Foo |      0 |     |       3 |            2 |     2 |
|   4 |        Bar |      1 |     |       3 |            1 |     1 |
|   5 |  Downloads |      1 |     |       4 |            3 |     3 |
+-----+------------+--------+     |       4 |            2 |     2 |
                                  |       4 |            1 |     1 |
                                  |       5 |            1 |     1 |
                                  +---------+--------------+-------+

I get all active menu entries with their ancestors easily with:

 SELECT menu.id, menu.title, GROUP_CONCAT(ancestors.ancestor_id) as ancestors
FROM menu, ancestors
WHERE menu.active = 1
GROUP BY (menu.id);

 +----+-----------+----------+
 | id |     title |ancestors |
 +----+-----------+----------+
 |  4 |       Bar | 3,2,1    | 
 |  5 | Downloads | 1        |
 +----+-----------+----------+

But how can I get all the the for the tree necessary ancestors, too? In my result I'd need the entry Foo and News so that I get a consistant tree. It should look like this:

 +----+-----------+----------+
 | id |     title |ancestors |
 +----+-----------+----------+
 |  2 |      News | 1        | 
 |  3 |       Foo | 2,1      | 
 |  4 |       Bar | 3,2,1    | 
 |  5 | Downloads | 1        |
 +----+-----------+----------+

How has the query to be like?

Answer 1

When I do this, I structure the ancestors table slightly differently. Instead of level, I store pathlength. Also store a row for each menu item to point to itself, with a path length of 0.

+---------+--------------+------------+
| menu_id |  ancestor_id | pathlength |
+---------+--------------+------------+
|       1 |            1 |          0 |
|       2 |            2 |          0 |
|       3 |            3 |          0 |
|       4 |            4 |          0 |
|       5 |            5 |          0 |
|       2 |            1 |          1 |
|       3 |            2 |          2 |
|       3 |            1 |          1 |
|       4 |            3 |          3 |
|       4 |            2 |          2 |
|       4 |            1 |          1 |
|       5 |            1 |          1 |
+---------+--------------+------------+

These "reflexive" entries allow you to join the set of active menu items to the closure table. Changing level to pathlength allows you to exclude the reflexive entries from the set of ancestors.

Now you can query all menu items that are ancestors of "active" menu items, including the active menu items themselves:

SELECT a2.menu_id, m2.title, GROUP_CONCAT(a2.ancestor_id) AS ancestors
FROM menu m1
JOIN ancestors a1 ON (m1.id = a1.menu_id)
JOIN ancestors a2 ON (a1.ancestor_id = a2.menu_id AND a2.pathlength > 0)
JOIN menu m2 ON (a2.menu_id = m2.id)
WHERE m1.active = 1
GROUP BY a2.menu_id;

Result:

+---------+-----------+-----------+
| menu_id | title     | ancestors |
+---------+-----------+-----------+
|       2 | News      | 1         | 
|       3 | Foo       | 2,1       | 
|       4 | Bar       | 3,2,1     | 
|       5 | Downloads | 1         | 
+---------+-----------+-----------+

Answer 2

Is there a easy way to manipulate the pathlength field when I insert or remove node?