How to find all IDs of children recursively?

Question

I would like to get all IDs from children in a tree with MySQL only.

I have a table like this:

ID parent_id name
1  0         cat1
2  1         subcat1
3  2         sub-subcat1
4  2         sub-subcat2
5  0         cat2

Now I'm trying to get all child IDs for cat1 (2,3,4) recursively. Is there any way how to achieve that?

Answer 1

There are two basic methods for doing this: adjacency lists and nested lists. Take a look at Managing Hierarchical Data in MySQL.

What you have is an adjacency list. No there isn't a way of recursively grabbing all descendants with a single SQL statement. If possible, just grab them all and map them all in code.

Nested sets can do what you want but I tend to avoid it because the cost of inserting a record is high and it's error-prone.

Answer 2

Here is a simple single-query MySql-solution:

SELECT GROUP_CONCAT(Level SEPARATOR ',') FROM (
   SELECT @Ids := (
       SELECT GROUP_CONCAT(`ID` SEPARATOR ',')
       FROM `table_name`
       WHERE FIND_IN_SET(`parent_id`, @Ids)
   ) Level
   FROM `table_name`
   JOIN (SELECT @Ids := <id>) temp1
) temp2

Just substitute <id> with the parent element's ID.

This will return a string with the IDs of all descendants of the element with ID = <id>, separated by ,. If you would rather have multiple rows returned, with one descendant on each row, you can use something like this:

SELECT *
FROM `table_name`
WHERE FIND_IN_SET(`ID`, (
   SELECT GROUP_CONCAT(Level SEPARATOR ',') FROM (
      SELECT @Ids := (
          SELECT GROUP_CONCAT(`ID` SEPARATOR ',')
          FROM `table_name`
          WHERE FIND_IN_SET(`parent_id`, @Ids)
      ) Level
      FROM `table_name`
      JOIN (SELECT @Ids := <id>) temp1
   ) temp2
))

Including the root/parent element

The OP asked for the children of an element, which is answered above. In some cases it might be useful to include the root/parent element in the result. Here are my suggested solutions:

Comma-separated string of ids:

SELECT GROUP_CONCAT(Level SEPARATOR ',') FROM (
   SELECT <id> Level
   UNION
   SELECT @Ids := (
       SELECT GROUP_CONCAT(`ID` SEPARATOR ',')
       FROM `table_name`
       WHERE FIND_IN_SET(`parent_id`, @Ids)
   ) Level
   FROM `table_name`
   JOIN (SELECT @Ids := <id>) temp1
) temp2

Multiple rows:

SELECT *
FROM `table_name`
WHERE `ID` = <id> OR FIND_IN_SET(`ID`, (
   SELECT GROUP_CONCAT(Level SEPARATOR ',') FROM (
      SELECT @Ids := (
          SELECT GROUP_CONCAT(`ID` SEPARATOR ',')
          FROM `table_name`
          WHERE FIND_IN_SET(`parent_id`, @Ids)
      ) Level
      FROM `table_name`
      JOIN (SELECT @Ids := <id>) temp1
   ) temp2
))

Answer 3

create table it should be look like below

DROP TABLE IF EXISTS `parent_child`;
CREATE TABLE `parent_child` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `parent_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=latin1;

insert  into `parent_child`(`id`,`name`,`parent_id`)
values (1,'cat1',0),(2,'subcat1',1),
(3,'sub-subcat1',2),(4,'sub-subcat2',2),
(5,'cat2',0);

Create function for getting parent child element

DELIMITER $$

USE `yourdatabase`$$

DROP FUNCTION IF EXISTS `GetAllNode1`$$

CREATE DEFINER=`root`@`localhost` FUNCTION `GetAllNode1`(GivenID INT) RETURNS TEXT CHARSET latin1
    DETERMINISTIC
BEGIN
    DECLARE rv,q,queue,queue_children TEXT;
    DECLARE queue_length,front_id,pos INT;
    SET rv = '';
    SET queue = GivenID;
    SET queue_length = 1;
    WHILE queue_length > 0 DO
        SET front_id = queue;
        IF queue_length = 1 THEN
            SET queue = '';
        ELSE
            SET pos = LOCATE(',',queue) + 1;
            SET q = SUBSTR(queue,pos);
            SET queue = q;
        END IF;
        SET queue_length = queue_length - 1;
        SELECT IFNULL(qc,'') INTO queue_children
        FROM (SELECT GROUP_CONCAT(id) AS qc
        FROM `parent_child` WHERE `parent_id` = front_id) A ;
        IF LENGTH(queue_children) = 0 THEN
            IF LENGTH(queue) = 0 THEN
                SET queue_length = 0;
            END IF;
        ELSE
            IF LENGTH(rv) = 0 THEN
                SET rv = queue_children;
            ELSE
                SET rv = CONCAT(rv,',',queue_children);
            END IF;
            IF LENGTH(queue) = 0 THEN
                SET queue = queue_children;
            ELSE
                SET queue = CONCAT(queue,',',queue_children);
            END IF;
            SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
        END IF;
    END WHILE;
    RETURN rv;
END$$

DELIMITER ;

write query for desire output

SELECT GetAllNode1(id) FROM parent_child 
or 
SELECT GetAllNode1(id) FROM parent_child  where id =1 //for specific parent's child element 

Answer 4

You could probably do it with a stored procedure, if that's an option for you.

Otherwise you can't do it with a single sql-statement.

Ideally you should make the recursive calls to walk the tree from your program

Answer 5

Your question seems a bit imprecise. Why do you want to have them, and what do you mean by having them, "in a tree" ?

The table you've got IS (the relational way to represent) the tree.

If you want them "in a table" with rows that hold the pairs (ID 4 , ParentID 0), then you need your SQL engine's version of recursive SQL to do this, if that engine supports it.

I wouldn't know about MySQL specifically, but my understanding is that they once planned to implement recursive SQL using the same syntax as Oracle, i.e. with CONNECT BY.

If you look in your manual's table of contents for keywords such as "recursive queries" or "CONNECT BY", I imagine you should be able to find the answer.

(Sorry for not being able to provide a more ready-to-consume answer.)