Рекурсивно проверять родителей ребенка в базе данных

Question

Я работаю в системе CMS, которая получает URL-адреса примерно так:

/ Parent1 / parent2 / ребенок /

Теперь легко проверить только ребенка, но, по моему мнению, вы также должны проверить, правильны ли родители и в правильном ли порядке. Проблема в том, что я не уверен, как это сделать.

Я использую mysql. Вот как будет выглядеть эта таблица:

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 ;

родительское поле содержит идентификаторы других страниц, которые будут использоваться в качестве родительского в родительском поле.

Answer 1

Вы можете изменить структуру таблицы SQL, чтобы использовать модель вложенных множеств для дерева; это значительно облегчает проверку на включение ребенка, который может быть глубоко вложен под конкретным родителем.

Эта страница содержит хорошее описание и сравнение модели списка смежности и вложенных множеств.

Может оказаться полезным следующий ответ на вопрос о вложенном множестве: Помощь при написании запроса SQL для вложенных множеств

Поднимите копию Деревья и иерархии Джо Селко в SQL для умников . Я продолжаю рекомендовать эту книгу, потому что она мне очень помогла, когда я моделировал древовидную структуру в SQL, используя вложенные множества.

Answer 2

Лучше всего получить полную таблицу за один запрос и создать вложенный массив. Со всей древовидной структурой в php гораздо проще проверить, правильны ли они.

В этом блоге есть информация о форматировании многоуровневого меню только с одним запросом: http://crisp.tweakblogs.net/blog/317/formatting-a-multi-level-menu-using-only-one-query.html

Идея заключается в том, что вы рекурсивно строите меню в php. Если вы можете изменить структуру вашей базы данных, вы также можете посмотреть на MPTT или Nested Sets. С этим механизмом намного легче следовать родительским / дочерним отношениям в дереве. Недостатком является то, что MPTT медленнее при вставке или обновлении узлов. Дополнительная информация: http://articles.sitepoint.com/article/hierarchical-data-database

Answer 3

Хорошо, я разработал свой собственный метод. Пожалуйста, не используйте кохану, поэтому я использую конструктор запросов коаны:

Этот фрагмент кода создает массив, который я хочу использовать.

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;
    }
}

И этот фрагмент кода выполняет URL через массив, который он застревает, если родитель ошибается:

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'];
}

Примечание. Данные, которые необходимо отправить для этой функции:

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

Answer 4

Если я правильно понял ваши требования, вы могли бы сделать что-то вроде этого (один вызов ТОЛЬКО БД, а НЕ ПОЛНОЕ ДЕРЕВО !!)

Полный сценарий можно найти здесь: http://pastie.org/1250062

Надеюсь, это поможет ...:)

Пример вызова хранимой процедуры

call page_parents(5);

call page_parents(7);

Пример сценария PHP

  <?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);