Mysql Query to select multi-level children from table

Question

This is my MySQL table layout of user table.
Is it possible to

1. Get the count of children under each person.
2. To select the person with at least 2 children under him.

+----+------+--------+
| id | Name | Parent |
+----+------+--------+
| 1  |    A |      0 |
+----+------+--------+
| 2  |    B |      0 |
+----+------+--------+
| 3  |    C |      1 |
+----+------+--------+
| 4  |    D |      3 |
+----+------+--------+
| 5  |    E |      2 |
+----+------+--------+

The expected answer are
1.

+----+------+----------+
| id | Name | Children |
+----+------+----------+
| 1  |    A |  2(C, D) |
+----+------+----------+
| 2  |    B |     1(E) |
+----+------+----------+
| 3  |    C |     1(D) |
+----+------+----------+
| 4  |    D |        0 |
+----+------+----------+
| 5  |    E |        0 |
+----+------+----------+

2.

+----+------+----------+
| id | Name | Children |
+----+------+----------+
| 1  |    A |  2(C, D) |
+----+------+----------+

Answer 1

Recursive queries are not supported by MySQL (edit: since I answer this question in 2014, MySQL 8.0 does support recursive queries), so this problem is quite awkward to solve if you store the data the way you store it (with parent indicating the hierarchical relationship).

You can store hierarchies in a few different ways to make this problem easier. I did a presentation about this here: Models for Hierarchical Data with SQL and PHP.

My favorite solution I call Closure Table. In this design, you use a second table to store all paths in the hierarchy. Include paths of length zero, which connect each node to itself, because this makes some tasks easier later.

CREATE TABLE TreePaths (
  ancestor INT NOT NULL,
  descendant INT NOT NULL,
  length INT NOT NULL DEFAULT 0
  PRIMARY KEY (ancestor, descendant)
);

INSERT INTO TreePaths VALUES
(1,1,0), (1,3,1), (1,4,2),
(2,2,0), (2,5,1),
(3,3,0), (3,4,1),
(4,4,0),
(5,5,0);

Then you can query all children for a given node:

SELECT descendant FROM TreePaths WHERE ancestor = 1 AND length > 0;

You can limit this to nodes with at least two children by grouping by ancestor and using HAVING to pick the group:

SELECT ancestor, COUNT(*), GROUP_CONCAT(descendant) FROM TreePaths WHERE length > 0
GROUP BY ancestor HAVING COUNT(*) >= 2;

Answer 2

if i read your questions, you need to know who is the child and grandchild. if that is true, try this one :

Select  a.id, a.name, 
        cast(
            (Case When b.name is Null Then 0 Else 1 End)+
            (Case When c.name is Null Then 0 Else 1 End)as Varchar(2)) +
        Case    When b.name is null Then ''
                When c.name is null Then '('+b.name+')'
                Else '('+b.name+','+c.name+')' End as Child
From [user] a
Left Join [user] b
    On b.parent = a.id
Left Join [user] c
    On c.parent = b.id

if you want to select the person with at least 2 children under him. you just add this filter :

Where (Case When b.name is Null Then 0 Else 1 End)+(Case When c.name is Null Then 0 Else 1 End) >= 2

Answer 3

As the comments show, recursive queries are not possible. So I fear, there will be no satisfying answer to your first question.

However in the second question you mention you want to have all superparent users, who have at least 2 children (and here I assume you mean at least two levels of children).

    SELECT id, name, CONCAT(level,children1,children2) AS children 
    FROM 
       (SELECT 
          t1.id, 
          t1.name, 
          IF(t2.name IS NOT NULL, t1.level + 1, t1.level) AS level, 
          IF(t1.children1 IS NULL, '', CONCAT('(',t1.children1)) AS children1, 
          IF(t2.name IS NULL, IF(t1.children1 IS NULL, '', ')'), CONCAT(', ', t2.name, ')')) AS children2 
        FROM 
          (SELECT u1.id, u1.name, u2.id AS bridge, u2.name AS children1, IF(u2.name IS NOT NULL, 1, 0) AS level 
           FROM users u1 
           LEFT JOIN users u2 ON u1.parent = 0 AND u2.parent = u1.id) t1 
        LEFT JOIN users t2 ON t2.parent = t1.bridge) x

This will retrieve all superparents (parent=0) and their first two levels of children (Answer to question 1 with a defined level). If you add

        WHERE level > 1

to the query, you will get the filtered list of all superparents who have at least 2 levels of children (Answer to question 2).

Getting all children to a superparent is actually only hard because in a row the parent value is saved but not the child's value (if in your schema elements do not have siblings). The other way around is fairly easy by using incremental variables. In your case, if you'd want to find the complete heritage of D, you could run

    SELECT t2.id, t2.name, level
    FROM (
        SELECT @r AS _id, (
            SELECT @r := parent 
            FROM users 
            WHERE id = _id
            ) AS parent, @l := @l + 1 AS level 
        FROM (
            SELECT @r := 4, @l := 0
            ) vars, users u 
        WHERE @r <> 0
        ) t1 
    JOIN users t2 ON t1._id = t2.id 
    ORDER BY t1.level DESC

where @r is initially set to D's id value. The query returns the element itself and each parent in separate row along with the reversed level:

id  name level
1   A    3
3   C    2
4   D    1

Of course, this can only be run separately for each element because of the dynamic variables, but it gives you the complete line from a child up to the uppermost parent.