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.

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

Answer 2

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

Answer 3

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

Answer 4

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