How to retrieve the path to a node in a tree - efficiently (related to the post 'parse a flat table into a tree?')

Question

This question is a follow up to this post:

http://stackoverflow.com/questions/192220/what-is-the-most-efficientelegant-way-to-parse-a-flat-table-into-a-tree

I liked the ClosureMap solution, but I have an additional problem to solve.

How can you easily retrieve the path to a particular node in a tree? For example, if you look at the tree provided:

ID Node Name

1 'Node 1'
2 'Node 1.1'
3 'Node 2'
4 'Node 1.1.1'
5 'Node 2.1'
6 'Node 1.2'

The path to 1.1.1 would be:

ID = 1, 2, 4

Without doing recursive SQL calls, is there an elegant way to retrieve a path?

Answer 1

SELECT ancestor_id
FROM ClosureTable
WHERE descendant_id = 4;

Returns the values 1, 2, 4. But they are returned on separate rows, and they give no indication that they're in the right order (we might not assume numerical order corresponds to tree hierarchy order).

Sometimes you would also store the depth for every path in the ClosureTable. But even if not, you can count how many ancestors a given node has, and use that to sort:

SELECT ct1.ancestor_id, COUNT(*) AS depth
FROM ClosureTable ct1
 JOIN ClosureTable ct2 ON (ct1.ancestor_id = ct2.descendant_id)
WHERE ct1.descendant_id = 4
GROUP BY ct1.ancestor_id
ORDER BY depth;

Yes, this still returns the result in three rows. If you use MySQL, you have access to GROUP_CONCAT(). Otherwise it's easy to fetch three rows and concatenate their values in application code.

Answer 2

I think I found the best solution, and didn't really realize it's in the post I referred to :).

Site Point had a nice article that shows the how to retrieve a specific node using the Left/Right attributes:

http://www.sitepoint.com/article/hierarchical-data-database/2/