MySQL recursive tree search

Question

I have a database with a tree of names that can go down a total of 9 levels deep and I need to be able to search down a signal branch of the tree from any point on the branch.

Database:

+----------------------+
| id |  name  | parent |
+----------------------+
| 1  |  tom   |   0    |
| 2  |  bob   |   0    |
| 3  |  fred  |   1    |
| 4  |  tim   |   2    |
| 5  |  leo   |   4    |
| 6  |  sam   |   4    |
| 7  |  joe   |   6    |
| 8  |  jay   |   3    |
| 9  |  jim   |   5    |
+----------------------+

Tree:

tom
 fred
  jay
bob
 tim
  sam
   joe
  leo
   jim

For example:

If I search "j" from the user "bob" I should get only "joe" and "jim". If I search "j" form "leo" I should only get "jim".

I can't think of any easy way do to this so any help is appreciated.

Answer 1

The new "recursive with" construct will do the job, but I don't know id MySQL supports it (yet).

with recursive bobs(id) as (
   select id from t where name = 'bob'
   union all
   select t.id from t, bobs where t.parent_id = bobs.id
)
select t.name from t, bobs where t.id = bobs.id
and name like 'j%'

Answer 2

You should really consider using the Modified Preorder Tree Traversal which makes such queries much easier. Here's your table expressed with MPTT. I have left the parent field, as it makes some queries easier.

+----------------------+-----+------+
| id |  name  | parent | lft | rght |
+----------------------+-----+------+
| 1  |  tom   |   0    |  1  |   6  |
| 2  |  bob   |   0    |  7  |  18  |
| 3  |  fred  |   1    |  2  |   5  |
| 4  |  tim   |   2    |  8  |  17  |
| 5  |  leo   |   4    | 12  |  15  |
| 6  |  sam   |   4    |  9  |  16  |
| 7  |  joe   |   6    | 10  |  11  |
| 8  |  jay   |   3    |  3  |   4  | 
| 9  |  jim   |   5    | 13  |  14  |
+----------------------+-----+------+

To search j from user bob you'd use the lft and rght values for bob:

SELECT * FROM table WHERE name LIKE 'j%' AND lft > 7 AND rght < 18

Implementing the logic to update lft and rght for adding, removing and reordering nodes can be a challenge (hint: use an existing library if you can) but querying will be a breeze.

Answer 3

You can do this with a stored procedure as follows:

Example calls

mysql> call names_hier(1, 'a');
+----+----------+--------+-------------+-------+
| id | emp_name | parent | parent_name | depth |
+----+----------+--------+-------------+-------+
|  2 | ali      |      1 | f00         |     1 |
|  8 | anna     |      6 | keira       |     4 |
+----+----------+--------+-------------+-------+
2 rows in set (0.00 sec)

mysql> call names_hier(3, 'k');
+----+----------+--------+-------------+-------+
| id | emp_name | parent | parent_name | depth |
+----+----------+--------+-------------+-------+
|  6 | keira    |      5 | eva         |     2 |
+----+----------+--------+-------------+-------+
1 row in set (0.00 sec)

$sqlCmd = sprintf("call names_hier(%d,'%s')", $id, $name);  // dont forget to escape $name
$result = $db->query($sqlCmd);

Full script

drop table if exists names;
create table names
(
id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
parent smallint unsigned null,
key (parent)
)
engine = innodb;

insert into names (name, parent) values
('f00',null), 
  ('ali',1), 
  ('megan',1), 
      ('jessica',3), 
      ('eva',3), 
         ('keira',5), 
            ('mandy',6), 
            ('anna',6);

drop procedure if exists names_hier;

delimiter #

create procedure names_hier
(
in p_id smallint unsigned,
in p_name varchar(255)
)
begin

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

set p_name = trim(replace(p_name,'%',''));

create temporary table hier(
 parent smallint unsigned, 
 id smallint unsigned, 
 depth smallint unsigned
)engine = memory;

insert into hier select parent, id, v_dpth from names where id = p_id;

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

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

while not v_done do

    if exists( select 1 from names n inner join tmp on n.parent = tmp.id and tmp.depth = v_dpth) then

        insert into hier select n.parent, n.id, v_dpth + 1 
            from names n inner join tmp on n.parent = tmp.id and tmp.depth = v_dpth;

        set v_dpth = v_dpth + 1;            

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

    else
        set v_done = 1;
    end if;

end while;


select 
 n.id,
 n.name as emp_name,
 p.id as parent,
 p.name as parent_name,
 hier.depth
from 
 hier
inner join names n on hier.id = n.id
left outer join names p on hier.parent = p.id
where
 n.name like concat(p_name, '%');

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

end #

delimiter ;

-- call this sproc from your php

call names_hier(1, 'a');
call names_hier(3, 'k');

Answer 4

There is no single SQL query that will return the data in tree format - you need processing to traverse it in the right order.

One way is to query MySQL to return MPTT:

SELECT * FROM table ORDER BY parent asc;

root of the tree will be the first item of the table, its children will be next, etc., the tree being listed "breadth first" (in layers of increasing depth)

Then use PHP to process the data, turning it into an object that holds the data structure.

Alternatively, you could implement MySQL search functions that given a node, recursively search and return a table of all its descendants, or a table of all its ancestors. As these procedures tend to be slow (being recursive, returning too much data that is then filtered by other criteria), you want to only do this if you know you're not querying for that kind of data again and again, or if you know that the data set remains small (9 levels deep and how wide?)

Answer 5

Have you thought about using a recursive loop? i use a loop for a cms i built on top of codeigniter that allows me to start anywhere in the site tree and will then subsequently filter trhough all the children> grand children > great grand children etc. Plus it keeps the sql down to short rapid queries opposed to lots of complicated joins. It may need some modifying in your case but i think it could work.

/**
 * build_site_tree
 *
 * @return void
 * @author Mike Waites
**/
public function build_site_tree($parent_id)
{
    return $this->find_children($parent_id);
}

/** end build_site_tree **/

// -----------------------------------------------------------------------

/**
 * find_children
 * Recursive loop to find parent=>child relationships
 *
 * @return array $children
 * @author Mike Waites
**/
public function find_children($parent_id)
{
    $this->benchmark->mark('find_children_start');

    if(!class_exists('Account_model'))
            $this->load->model('Account_model');

    $children = $this->Account_model->get_children($parent_id);

    /** Recursively Loop over the results to build the site tree **/
    foreach($children as $key => $child)
    {
        $childs = $this->find_children($child['id']);

        if (count($childs) > 0)
                $children[$key]['children'] = $childs;
    }

    return $children;

    $this->benchmark->mark('find_children_end');
}

/** end find_children **/

As you can see this is a pretty simplfied version and bear in mind this has been built into codeigniter so you will need to modyfy it to suite but basically we have a loop that calls itself adding to an array each time as it goes. This will allow you to get the whole tree, or even start from a point in the tree as long as you have the parent_id avaialble first!

Hope this helps

Answer 6

There isn't a nice/easy way of doing this; databases don't support tree-style data structures well.

You will need to work on a level-by-level basis to prune results from child-to-parent, or create a view that gives all 9 generations from a given node, and match using an OR on the descendants.