03.06.2011. 01:28

Nested Sets: Find Node by Path

Finding parent nodes in nested sets is easy, but how to detect node by path? Tried googling it, but found only questions, with no answers.

We could limit ordinary nested sets query to match only those elements that appear in path, but it won't work when paths are similar (and names are not unique, of course - otherwise it would be trivial). Searching for "ELECTRONICS/TELEVISIONS/LCD" could return "ELECTRONICS/TELEVISIONS/PORTABLE/LCD" and "ELECTRONICS/LCD/TELEVISIONS" as well - thus, we need to collect the exact path.

Based on data used in nested sets example as reference, you can retrieve full paths (and depths) of all nodes using:

SELECT node.name,
	GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '/') path,
	(COUNT(parent.name) - 1) level
FROM nested_category AS node, nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;
+----------------------+----------------------------------------------------+-------+
| name                 | path                                               | level |
+----------------------+----------------------------------------------------+-------+
| ELECTRONICS          | ELECTRONICS                                        |     0 |
| TELEVISIONS          | ELECTRONICS/TELEVISIONS                            |     1 |
| TUBE                 | ELECTRONICS/TELEVISIONS/TUBE                       |     2 |
| LCD                  | ELECTRONICS/TELEVISIONS/LCD                        |     2 |
| PLASMA               | ELECTRONICS/TELEVISIONS/PLASMA                     |     2 |
| PORTABLE ELECTRONICS | ELECTRONICS/PORTABLE ELECTRONICS                   |     1 |
| MP3 PLAYERS          | ELECTRONICS/PORTABLE ELECTRONICS/MP3 PLAYERS       |     2 |
| FLASH                | ELECTRONICS/PORTABLE ELECTRONICS/MP3 PLAYERS/FLASH |     3 |
| CD PLAYERS           | ELECTRONICS/PORTABLE ELECTRONICS/CD PLAYERS        |     2 |
| 2 WAY RADIOS         | ELECTRONICS/PORTABLE ELECTRONICS/2 WAY RADIOS      |     2 |
+----------------------+----------------------------------------------------+-------+
10 rows in set (0.00 sec)

Here, we collect parent names while performing nested sets query, and compose path using GROUP_CONCAT. Ordering by parent's left field while concatenating is mandatory, in order to get the valid path.

Using the above query, finding by path looks like this:

SELECT node.*, GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '/') path
FROM nested_category AS node, nested_category AS parent
WHERE node.name = 'LCD'
AND parent.name IN ('ELECTRONICS','TELEVISIONS','LCD')
AND node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
HAVING path="ELECTRONICS/TELEVISIONS/LCD"
ORDER BY node.lft;

Of course, you don't have to check for parent & node names in query, I've put these to narrow the search.

Btw, check out the Nested Intervals hybrid by Vadim Tropashko, a very fine idea.

Tags:MySQL