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, not further descendants!) 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.

Janniejanos

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.

Suitcase

"... I combined the nested set with adjacency lists ..." Ha! That's what I'm doing. I join an adj. list view, based on a query by Joe Celko. It just seems like an awful lot of code. Even the linked article's solution is ... verbose. – Janniejanos

I mean, compare selecting all the descendants of a node: SELECT * FROM nodes WHERE nodes.leftBound BETWEEN parentLeftBound AND parentRightBound; – Janniejanos

Well, the "child_view" is pretty simple, SELECT * FROM nodes WHERE parent_id = 123456 :D – Suitcase

+1 for "cheating." Typically when using a nested set model query time is more of a concern than the table building. I've found that adding a few other things like ParentId, and even Depth are extremely useful for certain cases and don't cost much to add to the table build. Hybrid nested set adjacency list tables are awesome. – Munford

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”.

Gonadotropin

I wonder which answer is better in performance, this one or the accepted post. However, both solutions do work. This one looks a bit more compact. – Sahara

For very large trees, we found this to perform poorly in MySQL and worse in SQL server because it requires a nested loop to be performed on the database. We changed our code to just retrieve all descendants, and then prune to just the children in our application code. – Scabrous

@Sahara This is very similar to the accepted answer, the difference is that instead of counting children and filtering to those with 1 child, it filters by seeing if ancestor is NULL.. That means it has less work to do (no sort and count step). It should be faster, but I have not tested it. – Prospective

@user393274 Your answer appears to be answering andreas (comparing methods), but it is not. You are answering about using SQL in general to get the children. – Prospective

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

Promisee

efm_files is the name of a table in my mysql database. Replace it with your own table name for your database. – Promisee

This is awesome - I'm using in a SQL db and your method works like a champ! – Ungulate

Answer 4

i know im doing a necro post, but here's my opinion.

why not include a "depth" column in your nested set? the depth column will indicate the "level" of an item.

so, to select the immediate childs of an item, just do

select c.*
from tree as p
join tree as c on (c.left > p.left and c.right < p.right and c.depth = p.dept + 1) where p.id = @parentID

Clapp

Because strictly speaking this is no longer a nested set, it is a combination of hierarchical models. And more often than not, changing the model to solve a problem isn't an option. – Applicatory

Answer 5

I'd go with a depth column, too. But use

SELECT Child.Node, Child.LEFT, Child.RIGHT
FROM Tree AS Child, Tree AS Parent
WHERE
        Child.Depth = Parent.Depth + 1
        AND Child.LEFT > Parent.LEFT
        AND Child.RIGHT < Parent.RIGHT
        AND Parent.LEFT = 1  -- Given Parent Node Left Index

Wikipedia

Fanchie

Note that it requires additional depth column along with left and right Id. – Littlefield

Answer 6

I found Wikipedia link has good minimized version of answer along with selected answer.

SELECT DISTINCT Child.Name
FROM ModelTable AS Child, ModelTable AS Parent 
WHERE Parent.Lft < Child.Lft AND Parent.Rgt > Child.Rgt  -- associate Child Nodes with ancestors
GROUP BY Child.Name
HAVING MAX(Parent.Lft) = @parentId  -- Subset for those with the given Parent Node as the nearest ancestor

And, any of you try to express it with Linq, please follow the link: https://mcmap.net/q/1020871/-linq-to-get-immediate-children-in-nested-set-model

Littlefield