Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Вывод дерева MySQL - Closure Table

 PHP.SU

 Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (1): [1]   

> Без описания
Поиск в теме | Версия для печати
Hapson
Отправлено: 24 Апреля, 2014 - 19:32:47
Post Id



Посетитель


Покинул форум
Сообщений всего: 356
Дата рег-ции: Июнь 2013  
Откуда: Ставропольский край


Помог: 10 раз(а)

[+]
Что-то я не могу никак отдуплить. Если для хранения дерева в MYSQL таблице используется метод Closure Table, то как можно вывести все дерево с сохранением структуры.
Ну допустим я хочу построить дерево категорий в форме в виде checkbox.

Есть вот такие таблицы:
Структура дерева
http://screenshotuploader[dot]com/s/1404o9y_m

Таблица данных
CODE (htmlphp):
скопировать код в буфер обмена
  1.  
  2. id      alias
  3. 9       programming
  4. 10      blog
  5. 11      php
  6. 12      mysql
  7. 14      php-functions
  8. 15      php-string
  9. 16      insert
  10. 17      delete
  11. 18      select
  12. 20      start_blog
  13.  


Таблица связей
CODE (htmlphp):
скопировать код в буфер обмена
  1.  
  2. parent  children
  3. 9       9
  4. 10      10
  5. 9       11
  6. 11      11
  7. 9       12
  8. 12      12
  9. 9       14
  10. 11      14
  11. 14      14
  12. 9       15
  13. 11      15
  14. 15      15
  15. 9       16
  16. 12      16
  17. 16      16
  18. 9       17
  19. 12      17
  20. 17      17
  21. 9       18
  22. 12      18
  23. 18      18
  24. 10      20
  25. 20      20
  26.  


Вывести потомков или предков одной категории - не проблема. Но как вытащить все дерево и правильно его построить?
(Добавление)
На ум приходит только одно решение - сделать еще одну табличку
CODE (htmlphp):
скопировать код в буфер обмена
  1. id    first_parent

Прикреплено изображение (Нажмите для увеличения)
Диаграмма1.png


-----
ПЫХ тут - ходи туда, прежде чем писать сюда (толку больше будет)
 
 Top
Мелкий Супермодератор
Отправлено: 24 Апреля, 2014 - 21:50:16
Post Id



Активный участник


Покинул форум
Сообщений всего: 11926
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 618 раз(а)
У вас какой-то странный closure table. Это точно он?
По моим данным там минимум 3 поля - ссылки на элемент, родителя и потомка.


-----
PostgreSQL DBA
 
 Top
Hapson
Отправлено: 24 Апреля, 2014 - 21:55:28
Post Id



Посетитель


Покинул форум
Сообщений всего: 356
Дата рег-ции: Июнь 2013  
Откуда: Ставропольский край


Помог: 10 раз(а)

[+]
Мелкий
Оно http://habrahabr[dot]ru/post/193166/
Третьим полем может быть уровень. А так, минимум два поля: родитель - потомок
(Добавление)
Упс, не ту ссылку дал, вот
https://coderwall[dot]com/p/lixing


-----
ПЫХ тут - ходи туда, прежде чем писать сюда (толку больше будет)
 
 Top
Мелкий Супермодератор
Отправлено: 25 Апреля, 2014 - 09:37:20
Post Id



Активный участник


Покинул форум
Сообщений всего: 11926
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 618 раз(а)
Hapson, да, точно, двух полей достаточно. Неправильно понял идею самой closure table (как, наверное, уже понятно - всерьёз я эту схему не изучал, по теме вопроса не подскажу).


-----
PostgreSQL DBA
 
 Top
esterio
Отправлено: 25 Апреля, 2014 - 10:37:29
Post Id



Активный участник


Покинул форум
Сообщений всего: 5025
Дата рег-ции: Нояб. 2012  
Откуда: Украина, Львов


Помог: 127 раз(а)
еще ссилкы по теме
http://karwin[dot]blogspot[dot]com/2010/[dot][dot][dot]sure-tables[dot]html
Но я также не смог понять как витащить все дерево со структурой
 
 Top
EuGen Администратор
Отправлено: 25 Апреля, 2014 - 12:33:16
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)
идея Closure table - хранить все узлы, стоящие выше по иерархии, чем тот, для которого нужно сделать запись. Это означает, что если у нас есть
PHP:
скопировать код в буфер обмена
  1.  
  2.     [P]
  3.    /   \
  4. [Q]    [R]
  5.       /   \
  6.    [S]     [T]
  7.  

То, например, для узла S записями будут
PHP:
скопировать код в буфер обмена
  1.  
  2. +--------+-------+
  3. | parent | child |
  4. +--------+-------+
  5. |   P    |   S   |
  6. +--------+-------+
  7. |   R    |   S   |
  8. +--------+-------+
  9. |   S    |   S   |
  10. +--------+-------+
  11.  

- сам себя узел тоже хранит. Поэтому, чтобы выбрать дерево для узла X, достаточно сделать запрос
CODE (SQL):
скопировать код в буфер обмена
  1. SELECT * FROM closure_table WHERE parent=X

- это выдаст все узлы, у которых X является родителем-предком - таким образом, будут получены все узлы.

Для именно вывода дерева closure table подходит не так хорошо, однако ничто не мешает сделать несколько запросов, начиная с листьев. Например:

- Найти листья. Это те узлы, которые встречаются в таблице всего лишь раз (то есть запись самих себя). Это выглядит примерно так:
CODE (SQL):
скопировать код в буфер обмена
  1. SELECT * FROM closure_table WHERE parent=X GROUP BY parent HAVING COUNT(1)=1

- Выбрать узлы, которые будут иметь в родителях X, а в качестве потомков - найденные листья. Это будет запрос на WHERE IN .. - что хорошо выполнится через range scan. Найденные узлы нужно рассортировать по листьям, поскольку нужно строить дерево и просто уровня уже недостаточно. Это, скорее всего, будет поручено приложению.
- Повторить до тех пор, пока есть записи.

В общем-то, запросов будет не так и много, но всё же запрос не будет один (несмотря на то, что всё дерево можно получить одним запросом).

Альтернатива - которой я бы рекомендовал пользоваться - выбрать всё дерево, а затем отдельно, в приложении, разбирать его. Это, конечно, потребует правильного построения массива, но все же это не так сложно. Этим можно воспользоваться, если размер данных не слишком велик.

Так как построение дерева "с листьев" - в общем-то, не очень простая задача, то можно хранить длину пути, чтобы получить возможность строить дерево с корня.

Ниже приведу пример, как можно поступить в случае с приложением. Вообще говоря, нам вовсе не обязательно хранить уровень - его можно вычислить (однако, как правило, лучше хранить и пересчитывать, так как вычисляется он исходя из количества записей в child-поле для конкретного узла). В примере я так и поступлю - то есть, не буду хранить уровень отдельно. Предположим, у нас есть дерево:

PHP:
скопировать код в буфер обмена
  1.  
  2.    [P]
  3.   /   \
  4. [Q]    [R]
  5.       /   \
  6.    [S]     [T]
  7.               \
  8.                [U]
  9.  

Тогда пусть его представлением будет массив:
PHP:
скопировать код в буфер обмена
  1. $data = [
  2.    ['parent'=>'P', 'child'=>'P'],
  3.    ['parent'=>'P', 'child'=>'Q'],
  4.    ['parent'=>'Q', 'child'=>'Q'],
  5.    ['parent'=>'P', 'child'=>'R'],
  6.    ['parent'=>'R', 'child'=>'R'],
  7.    ['parent'=>'P', 'child'=>'S'],
  8.    ['parent'=>'R', 'child'=>'S'],
  9.    ['parent'=>'S', 'child'=>'S'],
  10.    ['parent'=>'P', 'child'=>'T'],
  11.    ['parent'=>'R', 'child'=>'T'],
  12.    ['parent'=>'T', 'child'=>'T'],
  13.    ['parent'=>'P', 'child'=>'U'],
  14.    ['parent'=>'R', 'child'=>'U'],
  15.    ['parent'=>'T', 'child'=>'U'],
  16.    ['parent'=>'U', 'child'=>'U']
  17. ];

- я записываю его напрямую, но ничто не мешает выбирать данные из БД. Тогда в приложении мы можем рекурсивно собрать данные в привычную структуру со смежными подчинёнными узлами. Для этого нужно построить индекс-таблицу, в которой будет считаться как уровень узла, так и храниться его связи с остальными. В моём примере индекс двунаправленный (родители -> потомки, потомки->родители):
PHP:
скопировать код в буфер обмена
  1.    protected function indexClosure()
  2.    {
  3.       $this->indexTable = [];
  4.       foreach($this->closureTable as $item)
  5.       {
  6.          $this->indexTable['parents'][$item['parent']][] = $item['child'];
  7.          $this->indexTable['childs'][$item['child']][]   = $item['parent'];
  8.          $this->indexTable['levels']['forward'][$item['child']]     =
  9.             isset($this->indexTable['levels']['forward'][$item['child']])
  10.                ?$this->indexTable['levels']['forward'][$item['child']]+1
  11.                :1;
  12.       }
  13.       foreach($this->indexTable['levels']['forward'] as $key=>$level)
  14.       {
  15.          $this->indexTable['levels']['backward'][$level][]=$key;
  16.       }
  17.    }

-выношу это отдельно, так как понимание структуры этой вспомогательной индекс-таблицы очень важно. По сути, работая с индексированной таблицей в СУБД будет выполняться примерно та же работа. Использовать это можно так:
PHP:
скопировать код в буфер обмена
  1.    public function closureToAdjanced($node)
  2.    {
  3.       if(!isset($this->indexTable['parents'][$node]))
  4.       {
  5.          return [];
  6.       }
  7.       $level  = $this->indexTable['levels']['forward'][$node];
  8.       $tree   = array_intersect(
  9.          $this->indexTable['parents'][$node],
  10.          $this->indexTable['levels']['backward'][$level+1]
  11.       );    
  12.       $result = count($tree)
  13.          ?array_combine(
  14.             $tree,
  15.             array_fill(1, count($tree), [])
  16.           )
  17.          :[];
  18.       foreach($result as $child=>$subtree)
  19.       {
  20.          if(count($this->indexTable['parents'][$child])>1)
  21.          {
  22.             $result[$child] = $this->closureToAdjanced($child);
  23.          }
  24.       }
  25.       return $result;
  26.    }

- то есть, проверить, не лист ли передан, и, если нет, пройтись по поддереву рекурсивно. Поддерево - это все подчинённые узлы, у которых уровень на +1 больше. На этом всё.

Полный код:
PHP:
скопировать код в буфер обмена
  1. class ClosureTree
  2. {
  3.    protected $closureTable = [];
  4.    protected $indexTable = [];
  5.    
  6.    public function __construct(array $table=[])
  7.    {
  8.       $this->closureTable = $table;
  9.       $this->indexClosure();
  10.    }
  11.  
  12.    public function closureToAdjanced($node)
  13.    {
  14.       if(!isset($this->indexTable['parents'][$node]))
  15.       {
  16.          return [];
  17.       }
  18.       $level  = $this->indexTable['levels']['forward'][$node];
  19.       $tree   = array_intersect(
  20.          $this->indexTable['parents'][$node],
  21.          $this->indexTable['levels']['backward'][$level+1]
  22.       );    
  23.       $result = count($tree)
  24.          ?array_combine(
  25.             $tree,
  26.             array_fill(1, count($tree), [])
  27.           )
  28.          :[];
  29.       foreach($result as $child=>$subtree)
  30.       {
  31.          if(count($this->indexTable['parents'][$child])>1)
  32.          {
  33.             $result[$child] = $this->closureToAdjanced($child);
  34.          }
  35.       }
  36.       return $result;
  37.    }
  38.    //reset index & build it
  39.    protected function indexClosure()
  40.    {
  41.       $this->indexTable = [];
  42.       foreach($this->closureTable as $item)
  43.       {
  44.          $this->indexTable['parents'][$item['parent']][] = $item['child'];
  45.          $this->indexTable['childs'][$item['child']][]   = $item['parent'];
  46.          $this->indexTable['levels']['forward'][$item['child']]     =
  47.             isset($this->indexTable['levels']['forward'][$item['child']])
  48.                ?$this->indexTable['levels']['forward'][$item['child']]+1
  49.                :1;
  50.       }
  51.       foreach($this->indexTable['levels']['forward'] as $key=>$level)
  52.       {
  53.          $this->indexTable['levels']['backward'][$level][]=$key;
  54.       }
  55.    }
  56. }

И, как пример использования:
PHP:
скопировать код в буфер обмена
  1. $tree = new ClosureTree($data);
  2. var_dump($tree->closureToAdjanced('P'));


Результатом будет привычное
PHP:
скопировать код в буфер обмена
  1. array(2) {
  2.   ["Q"]=>
  3.   array(0) {
  4.   }
  5.   ["R"]=>
  6.   array(2) {
  7.     ["S"]=>
  8.     array(0) {
  9.     }
  10.     ["T"]=>
  11.     array(1) {
  12.       ["U"]=>
  13.       array(0) {
  14.       }
  15.     }
  16.   }
  17. }

- которое уже можно рекурсивно обходить, чтобы строить нужные отступы/форматирование.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Hapson
Отправлено: 25 Апреля, 2014 - 16:50:49
Post Id



Посетитель


Покинул форум
Сообщений всего: 356
Дата рег-ции: Июнь 2013  
Откуда: Ставропольский край


Помог: 10 раз(а)

[+]
EuGen
Спасибо за гору кода Улыбка
Цитата:

CODE (htmlphp):
скопировать код в буфер обмена
  1.  
  2.     [P]
  3.    /   \
  4. [Q]    [R]
  5.       /   \
  6.    [S]     [T]
  7.  

То, например, для узла S записями будут
CODE (htmlphp):
скопировать код в буфер обмена
  1.  
  2. +--------+-------+
  3. | parent | child |
  4. +--------+-------+
  5. |   S    |   P   |
  6. +--------+-------+
  7. |   S    |   R   |
  8. +--------+-------+
  9. |   S    |   S   |
  10. +--------+-------+
  11.  


Здесь видимо напутал.
Для S будет одна запись - S | S
И S будет в потомках P R T

Я думаю проще ввести еще одну таблицу, где хранить первого родителя. То есть совместить таблицу связей со списком смежностей. По первому родителю легко построить дерево. Выборка за один запрос. Вобщем вот такая идея хороша
https://coderwall[dot]com/p/lixing
Я так думаю


-----
ПЫХ тут - ходи туда, прежде чем писать сюда (толку больше будет)
 
 Top
EuGen Администратор
Отправлено: 25 Апреля, 2014 - 17:27:19
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)
В первом листинге - да, названия должны быть обратными. Всё дерево и так выбирается одним запросом. Но если нужно именно строить его где-либо для рекурсивных процедур, то - как я уже и указал выше - либо начинать с листьев, либо хранить/вычислять уровни. Второе мне кажется наилучшим вариантом.

При этом я всё ещё рекомендую форматирование поручать приложению, так как это именно его работа. Выбрать через СУБД - можно, однако пользы в этом почти что нет. Тем более, что при двойной индексации выбранного дерева в приложении операции будут происходить очень быстро (так как мы используем хеш-выборки)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Поиск в теме | Версия для печати
Страниц (1): [1]
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Вопросы новичков »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
  



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB