4

This question is a follow up to this post:

What is the most efficient/elegant 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?

Community
  • 1
  • 1
AndreLiem
  • 2,031
  • 5
  • 20
  • 26

2 Answers2

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.

Bill Karwin
  • 538,548
  • 86
  • 673
  • 828
  • Thanks... I should have analyze your solution more, that makes sense. – AndreLiem Aug 17 '09 at 20:10
  • To get the order, I suppose you can use the additional"path_length" field to retrieve by child to parent: SELECT ancestor_id FROM ClosureTable WHERE descendant_id = 4 ORDER BY path_length DESC; – AndreLiem Aug 17 '09 at 20:15
0

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/

AndreLiem
  • 2,031
  • 5
  • 20
  • 26
  • See above. I like Bill's solution much more than having to manage left/right attributes per node. – AndreLiem Aug 17 '09 at 20:11
  • The left/right solution is called "Nested Sets." It's efficient for queries, but it's pretty nasty when you need to change the tree. – Bill Karwin Aug 17 '09 at 20:15