MySQL: Get Root Node of Parent-Child Structure

Question

I have a table similar to this:

=================
| Id | ParentId |
=================
| 1  | 0        |
-----+-----------
| 2  | 1        |
-----+-----------
| 3  | 0        |
-----+-----------
| 4  | 3        |
-----+-----------
| 5  | 3        |
-----+-----------
| 6  | 0        |
-----+-----------
| 7  | 6        |
-----+-----------
| 8  | 7        |
-----------------

Given an Id, I need to know its root "node" Id. So,

Given 1, return 1
Given 2, return 1
Given 3, return 3
Given 4, return 3
Given 5, return 3
Given 6, return 6
Given 7, return 6
Given 8, return 7

There is no limit to the levels of the hierarchy. Is there a SQL that can do what I need?

score 10 · Answer 1 · answered Sep 06 '11 at 18:14

Actually, you can quite easily do this using a function.

Try running the following .sql script on your favorite empty test database.

--
-- Create the `Nodes` table
--
CREATE TABLE `Nodes` (
     `Id` INT NOT NULL PRIMARY KEY
    ,`ParentId` INT NOT NULL
) ENGINE=InnoDB;

--
-- Put your test data into it.
--
INSERT INTO `Nodes` (`Id`, `ParentId`)
VALUES 
  (1, 0)
, (2, 1)
, (3, 0)
, (4, 3)
, (5, 3)
, (6, 0)
, (7, 6)
, (8, 7);

--
-- Enable use of ;
--
DELIMITER $$

--
-- Create the function
--
CREATE FUNCTION `fnRootNode`
(
    pNodeId INT
)
RETURNS INT
BEGIN
    DECLARE _Id, _ParentId INT;

    SELECT pNodeId INTO _ParentId;

    my_loop: LOOP
        SELECT 
             `Id`
            ,`ParentId`
        INTO 
             _Id
            ,_ParentId
        FROM `Nodes`
        WHERE `Id` = _ParentId;

        IF _ParentId = 0 THEN
            LEAVE my_loop;
        END IF;
    END LOOP my_loop;

    RETURN _Id;
END;
$$

--
-- Re-enable direct querying
--
DELIMITER ;


--
-- Query the table using the function to see data.
--
SELECT 
     fnRootNode(`Nodes`.`Id`) `Root`
    ,`Nodes`.`Id`
    ,`Nodes`.`ParentId`
FROM `Nodes`
ORDER BY 
    fnRootNode(`Nodes`.`Id`) ASC
;

-- EOF

Output will be:

Root Id   ParentId
==== ==== ========
1    1    0
1    2    1
3    3    0
3    4    3
3    5    3
6    6    0
6    7    6
6    8    7

Best solution I've found so far. All others said that this was not possible due to MySQL not having recursive functions. +1 — BenMorel, Oct 03 '13 at 13:21

Magnar Myrtveit · Answer 2 · 2015-06-19T19:55:49.157

3

Here is a short query doing what you're asking, assuming your table is called foo and that you want to know the root of <id>:

SELECT f.Id
FROM (
    SELECT @id AS _id, (SELECT @id := ParentId FROM foo WHERE Id = _id)
    FROM (SELECT @id := <id>) tmp1
    JOIN foo ON @id <> 0
    ) tmp2
JOIN foo f ON tmp2._id = f.Id
WHERE f.ParentId = 0

edited Jun 19 '15 at 19:55

answered Jun 19 '15 at 19:50

Magnar Myrtveit

2,432
3
30
51

score 0 · Accepted Answer · answered Aug 05 '10 at 20:44

0

This is quite difficult to do in MySQL because it doesn't yet support recursive common table expressions.

I'd suggest instead using a nested sets model, or else storing the root node in the row and updating it as the structure changes.

answered Aug 05 '10 at 20:44

Mark Byers

811,555
193
1,581
1,452

score 0 · Answer 4 · answered Aug 05 '10 at 20:44

0

In short: no. Look at regular Bill Karwin's excellent presentation about hierarchical models and it's uses, shortcomings, and how to get around those: http://www.slideshare.net/billkarwin/models-for-hierarchical-data

answered Aug 05 '10 at 20:44

Wrikken

69,272
8
97
136

score 0 · Answer 5 · answered Dec 20 '16 at 11:37

I used @Kris answer for a while successfully, until I faced an issue where a child node might got deleted (accidentally), as a result the function gets into an infinite loop and hangs the mysql database at all, following is the modified version which works in my case:

DELIMITER $$

CREATE FUNCTION `FindRootNode`(InputValue INT(11)) RETURNS INT(11)
    NO SQL
BEGIN

DECLARE ReturnValue, _ParentId INT;

SELECT InputValue INTO _ParentId;

REPEAT
    SET ReturnValue = _ParentId;
    SELECT IFNULL((SELECT parent_id FROM TableName WHERE id=ReturnValue), 0) INTO _ParentId;

    UNTIL _ParentId = 0
END REPEAT;

RETURN ReturnValue;

END $$

DELIMITER ;

Usage1

SELECT CompanyCategoryTestRoot(HERE_COMES_CHILD_NODE_VALUE)

MySQL: Get Root Node of Parent-Child Structure

5 Answers5

Linked