Nested Set Model: Is there a simple way to query the children of a node?

Question

I've been using the crap out of the Nested Set Model lately. I have enjoyed designing queries for just about every useful operation and view. One thing I'm stuck on is how to select the immediate children (and only the children!) of a node.

To be honest, I do know of a way - but it involves unmanageable amounts of SQL. I'm sure there is a more straightforward solution.

Answer 1

Did you read the article you posted? It's under the heading "Find the Immediate Subordinates of a Node"

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) 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;

However, what I do (this is cheating) is I combined the nested set with adjacency lists -- I embed a "parent_id" in the table, so I can easily ask for the children of a node.

Answer 2

It seems to me this should be easily doable without the subqueries or parent column redundancy! For example, given parent's left and right are already known:

SELECT child.id
FROM nodes AS child
LEFT JOIN nodes AS ancestor ON
    ancestor.left BETWEEN @parentleft+1 AND @parentright-1 AND
    child.left BETWEEN ancestor.left+1 AND ancestor.right-1
WHERE
    child.left BETWEEN @parentleft+1 AND @parentright-1 AND
    ancestor.id IS NULL

That is, “from all descendents of the node in question, pick ones with no ancestor between themselves and the node”.

Answer 3

THIS ONE IS BETTER AND SMALLER

User "bobince" almost had it. I figured it out and got it to work for me because I have a little more MySQL experience than most. However, I can see why bobince's answer might scare people off. His query is incomplete. You need to select the parent_left and parent_right into mysql variables first.

The two queries below assume that your table is named tree, your left column is named lft, right column is named rgt, and that your primary key is named id. Change these values to suit your needs. Also, examine the first select statement. You will see that I am looking up the immediate descendants of node 5. Change the number 5 to look for children of whatever node you want.

I personally think this is a sleeker, sexier, and more efficient query than the others presented so far.

SELECT `lft`, `rgt` INTO @parent_left, @parent_right FROM efm_files WHERE `id` = 5;
SELECT `child.id`
FROM `tree` AS `child`
LEFT JOIN `tree` AS `ancestor` ON
    `ancestor`.`lft` BETWEEN @parent_left+1 AND @parent_right-1 AND
    `child`.`lft` BETWEEN `ancestor`.`lft`+1 AND `ancestor`.`rgt`-1
WHERE
    `child`.`lft` BETWEEN @parent_left+1 AND @parent_right-1 AND
    `ancestor`.`id` IS NULL

Answer 4

mrbinky3000, bobince: How would one go about using those queries without parameters/variables? I'm using sqlite which doesn't support that yet. Any ideas?