Recursively check the parents of a child in a database.

Question

I'm working on a CMS system that receives urls like this:

/parent1/parent2/child/

Now it's easy to check only the child but in my opinion you should also check if the parents are correct and in the right order. The problem is that I'm unsure on how to do this.

I'm using mysql. this is how that table would look:

CREATE TABLE IF NOT EXISTS `pages` (
  `id` int(11) NOT NULL auto_increment,
  `parent` int(11) NOT NULL default '0',
  `title` varchar(255) NOT NULL,
  `deleted` tinyint(1) NOT NULL default '0',
  PRIMARY KEY  (`id`),
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ;

the parent field keeps other page ID's that will be used as parent when in the parent field.

Answer 1

The best is to retreive the complete table in one query and build a nested array. With the whole tree structure in php, it's much easier to check if they are correct.

On this blog there is information about the formating of a multi level menu with only one query: http://crisp.tweakblogs.net/blog/317/formatting-a-multi-level-menu-using-only-one-query.html

The idea behind it is you build the menu recursively in php. If you're able to change your database structure, you can also look at MPTT, or Nested Sets. With this mechanism it's much easier to follow a parent/child relation in a tree. The disadvantage is MPTT is slower when you insert or update nodes. More information: http://articles.sitepoint.com/article/hierarchical-data-database

Answer 2

You could change your SQL table structure to use the nested sets model for a tree; it makes it much easier to test for inclusion of a child which may be deeply nested under a particular parent.

This page has a good description and comparison of the adjacency list model and nested sets.

You might find the following answer to a nested set question is also helpful: Help with writing a SQL query for Nested Sets

Pick up a copy of Joe Celko's Trees and Hierarchies in SQL for Smarties. I keep recommending this book because it helped me immensely when I was modelling a tree structure in SQL using nested sets.

Answer 3

If I understood your requirements correctly you could do something like this (one call to DB ONLY and NOT FULL TREE!!)

Full script can be found here : http://pastie.org/1250062

Hope it helps... :)

Example stored procedure call

call page_parents(5);

call page_parents(7);

Example PHP script

  <?php

function hasValidParents($conn, $urls, $pageID){
    $parents = array();
    $valid = true;

    //needs additional validation

    $sproc = sprintf("call page_parents(%d)", $pageID);

    $result = $conn->query($sproc);

    while($row = $result->fetch_assoc()) $parents[] = $row["page_id"];
    $result->close();   

    foreach($urls as $url)
        if($url && !in_array($url,$parents)){ $valid=false; break; }

    return $valid;
}

$urls = explode("/", "1/3/5"); // trim leading /

$conn = new mysqli("localhost", "foo_dbo", "pass", "foo_db", 3306);

echo hasValidParents($conn, $urls, $urls[count($urls)-1]) ? "true" : "false";

$conn->close();

?>

SQL

-- TABLES

drop table if exists pages;
create table pages
(
page_id smallint unsigned not null auto_increment primary key,
title varchar(255) not null,
parent_page_id smallint unsigned null,
key (parent_page_id)
)
engine = innodb;

-- TEST DATA

insert into pages (title, parent_page_id) values
('Page 1',null), 
('Page 2',null), 
   ('Page 1-2',1), 
      ('Page 1-2-1',3), 
      ('Page 1-2-2',3), 
   ('Page 2-1',2), 
   ('Page 2-2',2);


-- STORED PROCEDURES

drop procedure if exists page_parents;

delimiter #

create procedure page_parents
(
in p_page_id smallint unsigned
)
begin

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

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

insert into hier select parent_page_id, page_id, v_depth from pages where page_id = p_page_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 pages pg inner join hier on pg.page_id = hier.parent_page_id and hier.depth = v_depth) then

        insert into hier 
            select pg.parent_page_id, pg.page_id, v_depth + 1 from pages pg
            inner join tmp on pg.page_id = tmp.parent_page_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 
 pg.page_id,
 pg.title as page_title,
 b.page_id as parent_page_id,
 b.title as parent_page_title,
 hier.depth
from 
 hier
inner join pages pg on hier.page_id = pg.page_id
left outer join pages b on hier.parent_page_id = b.page_id
order by
 hier.depth, hier.page_id;

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

end #

delimiter ;

-- TESTING (call this stored procedure from php)

call page_parents(5);
call page_parents(7);

Answer 4

Ok I worked out my own method, Please not I'm using kohana so I'm using the query builder of kohana:

This piece of code builds the array I want to use.

public function build_array($parent = 0, $data = null)
{
    if(!$data)
    {
        $result = db::select('*')
            ->from($this->_table_name)
            ->as_assoc()
        ->execute($this->_db);

        foreach($result as $page)
        {
            $data['items'][$page['id']] = $page;
            $data['parents'][$page['parent']][] = $page['id']; 
        }
    }

    if (isset($data['parents'][$parent]))
    {
        $array = array();
        foreach ($data['parents'][$parent] as $item)
        {
            $array[$data['items'][$item]['slug']] = array(
                'id' => $data['items'][$item]['id'],
                'subitems' => $this->build_array($item, $data)
            );
        }
        return $array;
    }
}

And this piece of code runs the url trough the array it gets stuck if a parent is wrong:

public function get_id($page, $parents)
{    
    $array = $this->build_array();

    if(!empty($parents[0]))
    {
        foreach($parents as $parent)
        {
            $array = $array[$parent]['subitems'];
        }
    }

    return $array[$page]['id'];
}

Note: The data you need to send to this function is:

$page = 'child'; 
$parent = 'parent1/parent2';