CODEWITHSUNDEEP
sqlmysql
StackOverflowNewbie
StackOverflowNewbie

Reputation: 40653

MySQL: Get Root Node of Parent-Child Structure

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,

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

Upvotes: 5

Views: 5421

Answers (5)

AamirR
AamirR

Reputation: 12218

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)

Upvotes: 0

Magnar Myrtveit
Magnar Myrtveit

Reputation: 2760

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

Upvotes: 3

Kris
Kris

Reputation: 41867

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

Upvotes: 10

Wrikken
Wrikken

Reputation: 70540

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

Upvotes: 0

Mark Byers
Mark Byers

Reputation: 839074

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.

Upvotes: 0

Related Questions