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.

score 9 · Accepted Answer · edited Oct 14 '12 at 16:03

9

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.

edited Oct 14 '12 at 16:03

answered Mar 18 '09 at 18:39

Matt Rogish

24,435
11
76
92

"... 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. – Adam Siler Mar 18 '09 at 18:51
I mean, compare selecting _all_ the descendants of a node: SELECT * FROM nodes WHERE nodes.leftBound BETWEEN parentLeftBound AND parentRightBound; – Adam Siler Mar 18 '09 at 18:54
Well, the "child_view" is pretty simple, SELECT * FROM nodes WHERE parent_id = 123456 :D – Matt Rogish Mar 18 '09 at 18:57
+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. – Devin Apr 24 '17 at 18:39

bobince · Answer 2 · 2009-03-19T10:27:47.160

7

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

edited Mar 19 '09 at 10:27

answered Mar 19 '09 at 09:40

bobince

528,062
107
651
834

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. – andreas May 31 '13 at 23:43
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. – Matt Sgarlata Mar 20 '14 at 17:51
@andreas 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. – Ariel Jan 27 '16 at 00:54
@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. – Ariel Jan 27 '16 at 00:55

score 6 · Answer 3 · edited Aug 21 '13 at 16:18

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

efm_files is the name of a table in my mysql database. Replace it with your own table name for your database. — mrbinky3000, Dec 03 '12 at 19:14
This is awesome - I'm using in a SQL db and your method works like a champ! — JayTee, Nov 18 '20 at 16:12

score 0 · Answer 4 · edited May 23 '17 at 11:54

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://stackoverflow.com/a/25594386/361100

score 0 · Answer 5 · answered Feb 01 '11 at 03:33

0

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

answered Feb 01 '11 at 03:33

caydev2010

11
1

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. – Madbreaks Nov 20 '12 at 17:27

score 0 · Answer 6 · answered Nov 09 '11 at 07:54

0

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

answered Nov 09 '11 at 07:54

Valentin Klinghammer

1,319
1
13
19

Note that it requires *additional* depth column along with left and right Id. – Youngjae Sep 01 '14 at 01:44

Is there a simple way to query the children of a node?

6 Answers6

Linked