Determining "Number of Users below" in a multi-tier member database

Question

I've programmed a membership site for a client within which members join below other users. e.g.

userid | name  | subof
1      | John  | 0
2      | Joe   | 1
3      | Jill  | 0
4      | Janet | 2
5      | Juan  | 1
6      | George| 2

John and Jill are at the top, Joe and Juan are below John, and Janet and George are below Joe. The tier-ing is used for passing up commission. My client wants to be able to see How many users are below any given user, (at least it's restricted to 8 tiers out)

For now I have added the additional field `num_below` to the user table, and that field is incremented or decremented whenever someone joins or leaves below the user.

The first problem with this is that it feels like it violates good Database Normalization practices~ cuz it's storing data that's already in the DB

The second is that it get's hairy when my client comes and says "Oh, George meant to join under Juan, please move him"

I considered just dynamically calculating the number below every time it's asked for, but the db queries would seem to grow exponentially.

I've written a rectifySubs() function that can go through and fix all of the `num_below` fields, but as there are more members it will become more and more intensive to run~

function rectifySubs(){
    $NumBelow=array();//UID=>NUM_BELOW
    $SubOf=array();//UID=>IS_A_SUB_OF_UID
    $Uids=array();//UID
    $r=mysql_query("SELECT uid,subof FROM user");
    if(!$r || mysql_num_rows($r)==0){return 'Invalid';}
    while(list($uid,$subof)=mysql_fetch_row($r)){
        $NumBelow[$uid]=0;
        $SubOf[$uid]=$subof;
        $Uids[]=$uid;
    }
    mysql_free_result($r);

    $RungsUp=8;
    foreach($Uids as $uid){
        $r=1;
        $parent=$SubOf[$uid];
        while($parent>0 && $r<=$RungsUp){
            $NumBelow[$parent]+=1;
            $parent=$SubOf[$parent];
            $r++;
        }
    }
    $QueryByNum=array();
    foreach($NumBelow as $uid=>$num){
        if(!isset($QueryByNum[$num])){$QueryByNum[$num]=array();}
        $QueryByNum[$num][]=$uid;
    }
    unset($QueryByNum[0]);
    mysql_query("UPDATE user SET below=0");
    foreach($QueryByNum as $num=>$uids){
        $where=$or='';
        foreach($uids as $uid){
            $where.=$or."`uid`=".$uid;
            $or=" OR ";
        }
        mysql_query("UPDATE user SET below=".$num." WHERE ".$where);
    }
}

Any recommendations? I don't want to put too much redundant data in the DB, but going 8 tiers out every time seems way too processor intensive.

-- EDIT --

I wasn't clear enough about how the tiers worked so I made the table bigger. The key issue I'm addressing with the edit is that any person can have multiple people in a tier directly below them. Hope that makes sense.

-- SOLUTION -- (Implementation of Kakao's solution as a method of the 'Member' Class)

protected function getNumBelowAtLevel($i=1,$force=false){
    $i=abs((int)$i);
    if($i<=1){return 0;}//Level 1 is just the member themselves
    if($force || !isset($this->numBelow[$i])){
        $Us='';
        $Sels='';
        $Lefts='';
        $Groups='';
        $comma='';
        $nl='';
        for($k=1;$k<=$i-1;$k++){
            $j=$k==1?'0':$k-1;
            $Us.=$comma.'u'.$k;
            $Sels.=$comma.$nl.'m'.$k.'.mid as u'.$k;
            $Lefts.=$nl.'left join members as m'.$k.' on m'.$k.'.subof = m'.$j.'.mid';
            $Groups.=$comma.'u'.$k;

            $nl="\n\t\t\t\t\t";
            $comma=', ';
        }
        $sql="select count(*) - 1 as users_below
from (
    select distinct {$Us}
        from (
            select 
                {$Sels}
            from members as m0
                {$Lefts}
            where m0.mid = {$this->id}
                group by {$Groups} with rollup
            ) d
    ) a";
        if(DEBUG){var_dump($sql);}
        $r=mysql_query($sql);
        list($this->numBelow[$i])=mysql_fetch_row($r);
    }
    return $this->numBelow[$i];
}

Answer 1

select (case 
   when m1.userid is null then 0
   when m2.userid is null then 1
   when m3.userid is null then 2
   when m4.userid is null then 3
   when m5.userid is null then 4
   when m6.userid is null then 5
   when m7.userid is null then 6
   when m8.userid is null then 7
   else 8 end
   ) as users_below

from members as m0
left join members as m1 on m1.subof = m0.userid
left join members as m2 on m2.subof = m1.userid
left join members as m3 on m3.subof = m2.userid
left join members as m4 on m4.subof = m3.userid
left join members as m5 on m5.subof = m4.userid
left join members as m6 on m6.subof = m5.userid
left join members as m7 on m7.subof = m6.userid
left join members as m8 on m8.subof = m7.userid

where m0.userid = 1

Update

Multiple members below version:

select count(*) - 1 as users_below
from (
   select distinct u1, u2, u3, u4, u5, u6, u7
   from (
      select 
         m1.userid as u1, 
         m2.userid as u2, 
         m3.userid as u3,
         m4.userid as u4,
         m5.userid as u5,
         m6.userid as u6,
         m7.userid as u7

      from members as m0
      left join members as m1 on m1.subof = m0.userid
      left join members as m2 on m2.subof = m1.userid
      left join members as m3 on m3.subof = m2.userid
      left join members as m4 on m4.subof = m3.userid
      left join members as m5 on m5.subof = m4.userid
      left join members as m6 on m6.subof = m5.userid
      left join members as m7 on m7.subof = m6.userid

      where m0.userid = 1
      group by u1, u2, u3, u4, u5, u6, u7 with rollup
   ) d
) a

Answer 2

Personally, I think your solution of precomputing the data is just fine.

The one thing I would change is making the "rectify" function more smart in (optionally) not having to rebuild the entire dataset. If a person is moved to another branch the only ones that need to be recomputed are the person's old and new supers.

e.g., if Joe is moved from Bob to Alice, then Bob and all of his supers lost Joe's "num_below" and then Alice and all of her supers gain Joe's "num_below". Note that the "num_below" that is used to adjust the supers is actually num_below + 1 because of Joe himself isn't counted as part of his own.

Edit:

Alternatively, look at:

• http://articles.sitepoint.com/article/hierarchical-data-database/2

It's a different data structure that is easier to do this particular computation (number of children) along with others but does have it's own set of numbers (left/right) to maintain.

Answer 3

the following solution uses a non recursive stored procedure:

example usage:

call employees_hier(1);

+-----------+
| num_below |
+-----------+
|         7 |
+-----------+
1 row in set (0.00 sec)

hope you find it helpful - full script below :)

full script:

drop table if exists employees;
create table employees
(
emp_id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
boss_id smallint unsigned null,
key (boss_id)
)
engine = innodb;

insert into employees (name, boss_id) values
('f00',null), 
  ('ali later',1), 
  ('megan fox',1), 
      ('jessica alba',3), 
      ('eva longoria',3), 
         ('keira knightley',5), 
            ('liv tyler',6), 
            ('sophie marceau',7);

drop procedure if exists employees_hier;

delimiter #

create procedure employees_hier
(
in p_emp_id smallint unsigned
)
begin

declare v_done tinyint unsigned default(0);
declare v_dpth smallint unsigned default(0);

create temporary table hier(
 boss_id smallint unsigned, 
 emp_id smallint unsigned, 
 depth smallint unsigned
)engine = memory;

insert into hier select boss_id, emp_id, v_dpth from employees where emp_id = p_emp_id;

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

create temporary table emps engine=memory select * from hier;

while not v_done do

    if exists( select 1 from employees e inner join hier on e.boss_id = hier.emp_id and hier.depth = v_dpth) then

        insert into hier select e.boss_id, e.emp_id, v_dpth + 1 
            from employees e inner join emps on e.boss_id = emps.emp_id and emps.depth = v_dpth;

        set v_dpth = v_dpth + 1;            

        truncate table emps;
        insert into emps select * from hier where depth = v_dpth;

    else
        set v_done = 1;
    end if;

end while;

select count(*) as num_below from hier where depth > 0;

/*
-- use this if you want to return the employees instead

select 
 e.emp_id,
 e.name as emp_name,
 p.emp_id as boss_emp_id,
 p.name as boss_name,
 hier.depth
from 
 hier
inner join employees e on hier.emp_id = e.emp_id
left outer join employees p on hier.boss_id = p.emp_id;
*/

drop temporary table if exists hier;
drop temporary table if exists emps;

end #

delimiter ;

-- call this sproc from your php

call employees_hier(1);
call employees_hier(2);
call employees_hier(3);
call employees_hier(5);
call employees_hier(6);
call employees_hier(7);

Answer 4

I am adding some more people just to be clear I understand what you need:

userid | name  | subof
1      | John  | 0
2      | Joe   | 1
3      | Jill  | 0
4      | Janet | 2
5      | Dawn  | 4
6      | James | 4
7      | Mary  | 3
8      | Doug  | 6

So say your boss asks for the people under Joe. You want to get: Janet, Dawn, James, Doug -- right?

Instead of adding a new column, how about changing definition of subof (in my example I have made it a varchar)?

So your table would like this:

userid  name    subof   
1           John    0
2           Joe     0.1
3           Jill    0
4           Janet   0.1.2
5           Dawn    0.1.2.4
6           James   0.1.2.4
7           Mary    0.3
8           Doug    0.1.2.4.6

The top of the pyramid are 0, so John and Jill are still at the top. Then you know who is under each by the sequences following 0.

• changed john and jill to 0 instead of 0.0 to make updates easier

Doing it this way you could get the results you need in the following query:

    select * from temporary WHERE subof like '0.1.2%' ORDER BY userid ASC;
//this is joe's subof +'.'+ his userid

So your next issue is how to insert a new recruit. OK. Bill comes on under Doug. So what would the insert be for Bill?

// First get the subof and userid

SELECT subof, userid 
FROM tablename 
WHERE name = 'doug'; #answer 0.1.2.4.6
$subof, $userid = mysql_fetch; //pseudo code

//Then insert the new row which would be subof.userid

INSERT into tablename (userid, name, subof) VALUES ('9', 'Bill', '$subof.userid');

So now you have another row:

9   Bill    0.1.2.4.6.8

But wait ... there's more!

---

Replaced example with James and Doug for new table with George and Juan to focus on modified question:

===== new example with George and Juan

userid | name  | subof
1      | John  | 0
2      | Joe   | 0.1
3      | Jill  | 0
4      | Janet | 0.1.2
5      | Juan  | 0.1
6      | George| 0.1.2

John and Jill are at the top, Joe and Juan are below John, and Janet and George are below Joe. The tier-ing is used for passing up commission.

QUESTION

My client wants to be able to see How many users are below any given user, (at least it's restricted to 8 tiers out)

ANSWER

    SELECT count(*) 
    FROM tablename 
    WHERE subof LIKE 'subof_of_any_given_user+that_users_userid%';
//get those under Joe by using '0.1.2' (Joe's subof + his userid)

QUESTION

it get's hairy when my client comes and says "Oh, George meant to join under Juan, please move him"

ANSWER

SELECT userid, name, subof FROM tablename WHERE name in('Juan','George');

//$juan_userid = 5
//$juan_subof = 0.1
//$updatevalue = $juan_subof.'.'.$juan_userid; //0.1.5

//$george_userid = 6
//$george_subof = 0.1.2
/$subofmatch = $george_subof.'.'.$george_userid; //0.1.2.6

so your automated query would look something like this:

UPDATE tablename 
SET subof = (REPLACE(subof, '$george_subof', '$updatevalue')) 
WHERE (subof like '$subofmatch%' OR userid = '$george_userid')



 // here it is with number values to make it easier to understand //  
    UPDATE tablename 
    SET subof = (REPLACE(subof, '0.1.2', '0.1.5')) 
    WHERE (subof like '0.1.2.6%' OR userid = '6');

Giving you this new result:

userid  name    subof   
1           John    0
2           Joe     0.1
3           Jill    0
4           Janet   0.1.2
5           Juan    0.1
6           George  0.1.5

Enjoy!

Dawn