Count all child nodes of hierarchical data in a table

Question

I want to count number of all child nodes under any level of tree structure maintained in a table using adjacency model (parent-child key). Table structure and data looks like this:

id -  item-   parentid    
1  -  A   -   
2  -  B   -   1   
3  -  C   -   1   
4  -  D   -   2   
5  -  E   -   2   
6  -  F   -   3   
7  -  G   -   3   
8  -  H   -   5   
9  -  I   -   5   
10 -  J   -   9   
11 -  K   -   4

For example B has following child and grand child structure:

B
- E
  - H
  - I
    - J
- F
  - K

Now if you want to count "All child nodes of B" my answer should be 6.

Any pure SQL Query based solution would be of great help. Or mysql/php will also work.

Thanks!

There are a number of different ways to do this, which I've posted as answers to http://stackoverflow.com/questions/5995823/storing-hierarchical-data-mysql-for-referral-marketing. In order to determine which of these ways is appropraite, we need to know what kind of information you'd like to get from this table, and how frequently the table gets updated -- how frequently information is added and deleted, and what's supposed to happen if something gets deleted from the middle of the hierarchy. Could you elaborate more on what you want to do with this hierarchy? — Ken Bloom, May 19 '11 at 15:37
This is simple enough in an SQL platform, and the solution uses recursion. But for a NONsql such as yours, and for platforms that do not have recursion, you have to use a procedure and a temp table. — PerformanceDBA, May 30 '15 at 09:31
I have a solution using php and MySql, check my [response](https://stackoverflow.com/a/67035058/15424227). I get the tree structure using one query, and implement two recursive function to count all children nodes of each node in a tree (hierarchical data structure). — nachospiu, Apr 10 '21 at 13:57

score 3 · Answer 1 · answered May 19 '11 at 15:27

3

The way you store your data will not allow for a simple query to get the total child count. But have a look at:

http://en.wikipedia.org/wiki/Nested_set_model

Where a query like this would be possible.

answered May 19 '11 at 15:27

Yoshi

54,081
14
89
103

3

+1, or directly compare different models here: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html – Unreason May 19 '11 at 15:29
@Unreason Yeah, I've come accross that article so many times, but didn't remember it now. ;D – Yoshi May 19 '11 at 15:30
@Unreason, Yoshi: It disappeared at this location, here is the new one: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ – Paŭlo Ebermann Aug 05 '11 at 16:56

score 3 · Answer 2 · answered May 19 '11 at 15:31

Below is a PHP based solution:

function countChildren($startId) {
    $directDescendents = *_query("SELECT id FROM Table WHERE parentid = ?", array( $startId ));
    $count = *_num_rows($directDescendents);
    while($row = *_fetch_array($directDescendents))
        $count += countChildren($row['id']);
    return $count;
}

$numChildren = countChildren(2); // Number of Children for 'B'

Replace *_num_rows and *_fetch_array with whatever functions for the SQL extension you are using. This won't be as efficient as a pure SQL solution, but it will work. The way I'm querying in the function is assuming bound parameters, but execute the query as you like.

Depending on the size of the table and depth of the branch it might be much more efficient to retrieve the whole table and do the walk/count in memory instead of issuing multiple select statements (also the reverse might be true). — Unreason, May 19 '11 at 15:47

score 3 · Answer 3 · answered May 19 '11 at 15:47

Can be done fairly simply with a non-recursive stored procedure as follows:

Example calls

mysql> call category_hier(1);
+--------------+
| num_children |
+--------------+
|            3 |
+--------------+
1 row in set (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql> call category_hier(2);
+--------------+
| num_children |
+--------------+
|            2 |
+--------------+
1 row in set (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

Full script

drop table if exists categories;
create table categories
(
cat_id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
parent_cat_id smallint unsigned null,
key (parent_cat_id)
)
engine = innodb;

insert into categories (name, parent_cat_id) values
('Location',null), 
('Color',null), 
   ('USA',1), 
      ('Illinois',3), 
      ('Chicago',3), 
   ('Black',2), 
   ('Red',2);


drop procedure if exists category_hier;
delimiter #

create procedure category_hier
(
in p_cat_id smallint unsigned
)
begin

declare v_done tinyint unsigned default 0;
declare v_depth smallint unsigned default 0;

create temporary table hier(
 parent_cat_id smallint unsigned, 
 cat_id smallint unsigned, 
 depth smallint unsigned default 0
)engine = memory;

insert into hier select parent_cat_id, cat_id, v_depth from categories where cat_id = p_cat_id;
create temporary table tmp engine=memory select * from hier;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

while not v_done do

    if exists( select 1 from categories c
        inner join tmp on c.parent_cat_id = tmp.cat_id and tmp.depth = v_depth) then

        insert into hier select c.parent_cat_id, c.cat_id, v_depth + 1 from categories c
            inner join tmp on c.parent_cat_id = tmp.cat_id and tmp.depth = v_depth;

        set v_depth = v_depth + 1;          

        truncate table tmp;
        insert into tmp select * from hier where depth = v_depth;

    else
        set v_done = 1;
    end if;

end while;

/*
select 
 c.cat_id,
 c.name as category_name,
 p.cat_id as parent_cat_id,
 p.name as parent_category_name,
 hier.depth
from 
 hier
inner join categories c on hier.cat_id = c.cat_id
left outer join categories p on hier.parent_cat_id = p.cat_id
order by
 hier.depth;
*/

select count(*) as num_children from hier where parent_cat_id is not null;

drop temporary table if exists hier;
drop temporary table if exists tmp;

end #

delimiter ;

call category_hier(1);

call category_hier(2);

You can easily adapt this example to suit your requirements.

Hope it helps :)

Count all child nodes of hierarchical data in a table

3 Answers3

Linked

Related