MySQL Nested Sets - How to find parent of node?

Question

I have your run of the mill nested set hierarchy type setup with the following columns:

table name:

myset

columns:

id, name, lft, rgt

Does anyone know a query to determine the parent of a node?

I read a couple places that it's handy to also have a parent_id column in your table to keep track of this, but it seems redundant and it seems like it could get out of sync with the nested set if a query was incorrectly executed when adding/removing/moving anything within the set.

Hammered

Answer 1

Look at this question. It is similar to yours. I have posted there a query you may need.

SELECT title, (SELECT TOP 1 title 
           FROM tree t2 
           WHERE t2.lft < t1.lft AND t2.rgt > t1.rgt    
           ORDER BY t2.rgt-t1.rgt ASC) AS parent
FROM tree t1
ORDER BY rgt-lft DESC

I hope there is what you need.

For the following table:

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |

it produces the output:

title                | parent
----------------------------------------------
ELECTRONICS          | NULL
PORTABLE ELECTRONICS | ELECTRONICS
TELEVISIONS          | ELECTRONICS
MP3 PLAYERS          | PORTABLE ELECTRONICS
FLASH                | MP3 PLAYERS
CD PLAYERS           | PORTABLE ELECTRONICS
2 WAY RADIOS         | PORTABLE ELECTRONICS
TUBE                 | TELEVISIONS
LCD                  | TELEVISIONS
PLASMA               | TELEVISIONS

Urumchi

Do you know why the ORDER BY t2.rgt-t1.rgt will return an error in sqlite? SQLSTATE[HY000]: General error: 1 no such column: t1.rgt ... it works when i remove t1.rgt from order by so it seems to be an issue with order by... – Questionnaire

Answer 2

TOP is a MSSQL command, use LIMIT for MySQL:

SELECT title, (SELECT title 
       FROM tree t2 
       WHERE t2.lft < t1.lft AND t2.rgt > t1.rgt    
       ORDER BY t2.rgt-t1.rgt ASC
       LIMIT 1) 
AS parent FROM tree t1 
ORDER BY (rgt-lft) DESC

Should do the trick ..

Cozza

Answer 3

just to add to these answers which helped me out a lot,

i needed to find the immediate parent of a node, as well as the very top level parent of a node chain in some instances,

i used the following as a base to get the items in child-to-parent order

SELECT parent.*  FROM
        nested_set node,
        nested_set parent
        WHERE (
            node.set_left BETWEEN parent.set_left AND parent.set_right          
        )
        AND node.set_id={CHILD_NODE_ID_HERE}
        ORDER BY parent.set_right - parent.set_left
        #LIMIT 1,1

it is then a matter of adding the LIMIT 1,1 to only capture the second row which would be the immediate parent

it should also be noted that with the above query if the node itself is the very top level parent, then it would NOT have an immediate parent, so with the LIMIT 1,1 it should return an empty result set

to get the very top level parent i reversed the order by clause, included a check if the node itself is the top parent,and limited the result to the first row

SELECT parent.* AS top_level_right FROM
        nested_set node,
        nested_set parent
        WHERE (
            node.set_left >= parent.set_left 
            AND node.set_left <= parent.set_right
        )
        AND node.set_id={CHILD_NODE_ID_HERE}
        ORDER BY parent.set_left - parent.set_right
        LIMIT 1

in the last query i used >= <= operators so that the selected range encompasses the child node if it also happens to be the top level parent

Uncommercial

Why use order by parent.set_left - parent.set_right ASC and not order by parent.lft desc? Your method is looking for the smallest gap, mine just gets the immediate parent using a faster method. – Flavorsome

Answer 4

I had a problem with Lucasz's query. My version of mysql didn't understand the TOP command. I had to use LIMIT instead. Here is the revised code.

SELECT 
   `id`, 
   (SELECT 
      `id`
    FROM 
       `[*** YOUR TABLE ***]` AS `t2` 
    WHERE 
       `t2`.`left_id`  < `t1`.`left_id`AND 
       `t2`.`right_id` > `t1`.`right_id`
    ORDER BY 
       `t2`.`right_id`-`t1`.`right_id`ASC 
    LIMIT 
       1) AS `parent`
FROM 
    `[*** YOUR TABLE ***]` AS `t1`
WHERE 
    `t1`.`id` = [*** ID OF THE NODE WHOS PARENT YOU WISH TO LOOKUP ***]
ORDER BY 
    `right_id`-`left_id` DESC

Obviously, change the stuff in the [ ]'s to suit your needs. Also remove the [ ]'s. This query only returns ONE row. Like so...

id  parent
7   3

Harangue

Answer 5

SELECT parent.name 
FROM myset AS node, myset AS parent 
WHERE parent.lft < node.lft 
AND parent.rgt > node.rgt 
AND node.id = {YOUR CATEGORY ID} 
ORDER BY ( parent.rgt - parent.lft ) ASC LIMIT 1;

Hallucinate

Answer 6

select * from myset
  where lft < :lftOfCurrent and rgt > :lftOfCurrent
  order lft desc
  limit 1

You could use a max rather than order/ limit and you might need another keyword to limit the results to one row depending on your database. Between rather than < and > would work if your database returns the exclusive set, which MySQL doesn't.

Kuopio

Answer 7

All ancestors are returned by

SELECT id FROM thetable
WHERE x BETWEEN lft and rgt;

So, the direct parent is the ancestor with the smallest difference between lft and rgt.

SELECT id FROM thetable
WHERE x BETWEEN lft and rgt
ORDER BY (rgt-lft)
LIMIT 1

Conjectural

if your x should be the id of the element, than your statements are wrong. – Arther

Answer 8

The code from spankmaster79 was not completely wrong. I modified his code and it worked.

SELECT parent . * FROM Nested_Category AS node, Nested_Category AS parent 
enter code hereWHERE node.leftSide
BETWEEN parent.leftSide
AND parent.rightSide
AND node.id ='Enter the Node ID'
ORDER BY (
parent.rightSide - parent.leftSide
)
LIMIT 1 , 1

Slick