Управление иерархическими данными в MySQL

default/fileshierarchical data mysql Оригинал заметки Управление иерархическими данными в MySQL (Managing Hierarchical Data in MySQL By Mike Hillyer) получилось найти только на зеркале Яндекса. Спасибо ему за это. Автор заметки также рекомендует познакомится с книгой Джо Селко Joe Celko's Trees and Hierarchies in SQL for Smarties (у него есть еще книга SQL для профессионалов. Программирование) и заметкой Storing Hierarchical Data in a Database

Управление иерархическими данными в MySQL

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

Эти категории образуют иерархию, подобно примерам, приведенным выше. В этой статье мы рассмотрим две модели для работы с иерархическими данными в MySQL, начиная с традиционной моделью список смежности (Adjacency List Model).

Модель Список смежности (Adjacency List Model)

Как правило, примеры указанные выше, будут храниться в таблице с следующим определением (я включаю в пример все выражения CREATE и INSERT, чтобы мы смогли следить вместе за ходом мысли):

  1. CREATE TABLE category(
  2. category_id INT AUTO_INCREMENT PRIMARY KEY,
  3. name VARCHAR(20) NOT NULL,
  4. parent INT DEFAULT NULL);
  5.  
  6.  
  7. INSERT INTO category
  8. VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
  9. (4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
  10. (7,'MP3 PLAYERS',6),(8,'FLASH',7),
  11. (9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);
  12.  
  13. SELECT * FROM category ORDER BY category_id;
  14.  
  15. +-------------+----------------------+--------+
  16. | category_id | name | parent |
  17. +-------------+----------------------+--------+
  18. | 1 | ELECTRONICS | NULL |
  19. | 2 | TELEVISIONS | 1 |
  20. | 3 | TUBE | 2 |
  21. | 4 | LCD | 2 |
  22. | 5 | PLASMA | 2 |
  23. | 6 | PORTABLE ELECTRONICS | 1 |
  24. | 7 | MP3 PLAYERS | 6 |
  25. | 8 | FLASH | 7 |
  26. | 9 | CD PLAYERS | 6 |
  27. | 10 | 2 WAY RADIOS | 6 |
  28. +-------------+----------------------+--------+
  29. 10 rows in set (0.00 sec)

В модели списка смежности, каждый элемент таблицы содержит указатель на его родителя. Самый верхний элемент, в данном случае ELECTRONICS, имеет значение NULL для его родителей. Модель список смежности имеет преимущество, довольно легко можно увидеть, что FLASH является дочерним MP3 PLAYERS, который является дочерним для портативной электроники, который является дочерним электроники. В то время как модель списка смежности довольно легка в реализации, может возникнуть проблема при реализации на SQL.

Получение полного дерева

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

  1. SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
  2. FROM category AS t1
  3. LEFT JOIN category AS t2 ON t2.parent = t1.category_id
  4. LEFT JOIN category AS t3 ON t3.parent = t2.category_id
  5. LEFT JOIN category AS t4 ON t4.parent = t3.category_id
  6. WHERE t1.name = 'ELECTRONICS';
  7. +-------------+----------------------+--------------+-------+
  8. | lev1 | lev2 | lev3 | lev4 |
  9. +-------------+----------------------+--------------+-------+
  10. | ELECTRONICS | TELEVISIONS | TUBE | NULL |
  11. | ELECTRONICS | TELEVISIONS | LCD | NULL |
  12. | ELECTRONICS | TELEVISIONS | PLASMA | NULL |
  13. | ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |
  14. | ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS | NULL |
  15. | ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL |
  16. +-------------+----------------------+--------------+-------+
  17. 6 rows in set (0.00 sec)

Просмотр всех узлов лист

Мы можем найти все конечные узлы в дереве (т.е. без детей) с помощью

  1. LEFT JOIN, запрос:
  2. SELECT t1.name FROM
  3. category AS t1 LEFT JOIN category as t2
  4. ON t1.category_id = t2.parent
  5. WHERE t2.category_id IS NULL;
  6.  
  7.  
  8. +--------------+
  9. | name |
  10. +--------------+
  11. | TUBE |
  12. | LCD |
  13. | PLASMA |
  14. | FLASH |
  15. | CD PLAYERS |
  16. | 2 WAY RADIOS |
  17. +--------------+

Получение одного пути
Объединение также позволяет нам увидеть полный путь нашей иерархии:
  1. SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
  2. FROM category AS t1
  3. LEFT JOIN category AS t2 ON t2.parent = t1.category_id
  4. LEFT JOIN category AS t3 ON t3.parent = t2.category_id
  5. LEFT JOIN category AS t4 ON t4.parent = t3.category_id
  6. WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';
  7. +-------------+----------------------+-------------+-------+
  8. | lev1 | lev2 | lev3 | lev4 |
  9. +-------------+----------------------+-------------+-------+
  10. | ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |
  11. +-------------+----------------------+-------------+-------+
  12. 1 row in set (0.01 sec)

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

Ограничения Примерного Списка смежности

Работа с моделью список смежности в чистом SQL может быть затруднена в лучшем случае. Перед тем как увидеть полный путь к категории мы должны знать, на каком уровне она находится. Кроме того, особое внимание должно быть уделено удалению узлов из-за возможности сиротства всей ветки (удалить категорию портативной электроники категории и всех ее детей-сирот). Некоторые из этих ограничений могут быть решены с помощью клиентского кода или хранимых процедур. С процедурным языком, мы можем начать с нижней части дерева и повторять вверх возврат полного дерева или одного пути. Мы также можем использовать процедурное программирование для удаления узлов всей ветки без сиротства, продвигая один дочерний элемент и изменяя порядок расположения остальных детей, чтобы указать на нового родителя.

Модель вложенных множеств (The Nested Set Model)

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

Обратите внимание, что наша иерархия по-прежнему сохраняется, родительские категории сохраняют дочерние. Мы представляем эту форму иерархии в таблице с помощью указателей на левые и правые узлы в наших множествах:

  1. CREATE TABLE nested_category (
  2. category_id INT AUTO_INCREMENT PRIMARY KEY,
  3. name VARCHAR(20) NOT NULL,
  4. lft INT NOT NULL,
  5. rgt INT NOT NULL
  6. );
  7.  
  8.  
  9. INSERT INTO nested_category
  10. VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
  11. (4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),
  12. (7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
  13. (9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);
  14.  
  15.  
  16. SELECT * FROM nested_category ORDER BY category_id;
  17.  
  18.  
  19. +-------------+----------------------+-----+-----+
  20. | category_id | name | lft | rgt |
  21. +-------------+----------------------+-----+-----+
  22. | 1 | ELECTRONICS | 1 | 20 |
  23. | 2 | TELEVISIONS | 2 | 9 |
  24. | 3 | TUBE | 3 | 4 |
  25. | 4 | LCD | 5 | 6 |
  26. | 5 | PLASMA | 7 | 8 |
  27. | 6 | PORTABLE ELECTRONICS | 10 | 19 |
  28. | 7 | MP3 PLAYERS | 11 | 14 |
  29. | 8 | FLASH | 12 | 13 |
  30. | 9 | CD PLAYERS | 15 | 16 |
  31. | 10 | 2 WAY RADIOS | 17 | 18 |
  32. +-------------+----------------------+-----+-----+

Мы используем lft и rgt, потому что left и right являются зарезервированными словами MySQL см. http://dev.mysql.com/doc/mysql/en/reserved-words.html полный список зарезервированных слов.

Так как же нам определить левое и правое значения? Мы начинаем нумерацию с левой стороны внешних узлов и продолжать вправо:

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

При работе с деревом, мы работаем слева направо, один слой за один другим, спускаясь на детей каждого узла, прежде чем присвоим rgt и перейдем на право. Такой подход называется изменение алгоритмом прямого обхода дерева (preorder tree traversal algorithm).

Получение полного дерева

Мы можем получить полное дерево с помощью объединения, которое связывает родителей с узлами на основании, что lft значение узла будет всегда появляться между lft своих родителей и значением rgt:

  1. SELECT node.name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. AND parent.name = 'ELECTRONICS'
  6. ORDER BY node.lft;
  7.  
  8.  
  9. +----------------------+
  10. | name |
  11. +----------------------+
  12. | ELECTRONICS |
  13. | TELEVISIONS |
  14. | TUBE |
  15. | LCD |
  16. | PLASMA |
  17. | PORTABLE ELECTRONICS |
  18. | MP3 PLAYERS |
  19. | FLASH |
  20. | CD PLAYERS |
  21. | 2 WAY RADIOS |
  22. +----------------------+

В отличие от нашего предыдущего примера с моделью список смежности, этот запрос будет работать независимо от глубины дерева. Мы не касаемся со значением rgt узла в нашем предикате BETWEEN, так как значение rgt всегда подпадают под те же родители, что и lft значения.

Нахождение всех конечных узлов

Нахождение всех конечных узлов в модели вложенных множеств даже проще, чем LEFT JOIN метод используемый в модели списка смежности. Если вы посмотрите на таблицу nested_category, вы можете заметить, что LFT и RGT значения для конечных узлов являются последовательными числами. Чтобы найти конечных узлов, мы ищем узлы, где rgt = lft+ 1:

  1. SELECT name
  2. FROM nested_category
  3. WHERE rgt = lft + 1;
  4.  
  5.  
  6. +--------------+
  7. | name |
  8. +--------------+
  9. | TUBE |
  10. | LCD |
  11. | PLASMA |
  12. | FLASH |
  13. | CD PLAYERS |
  14. | 2 WAY RADIOS |
  15. +--------------+

Получение одного путь

При модель вложенных множеств, мы можем получить один путь, не образуя несколько объединений таблиц:

  1. SELECT parent.name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. AND node.name = 'FLASH'
  6. ORDER BY parent.lft;
  7.  
  8. +----------------------+
  9. | name |
  10. +----------------------+
  11. | ELECTRONICS |
  12. | PORTABLE ELECTRONICS |
  13. | MP3 PLAYERS |
  14. | FLASH |
  15. +----------------------+

Определение глубины узлов

Мы уже рассмотрели, как показывают все дерево целиком, но что, если мы хотим также показать глубину каждого узла в дереве, чтобы лучше определить, как каждый узел размещается в иерархии? Это может быть сделано путем добавления функции COUNT и предиката (клауза) GROUP BY для наших существующих запросов для отображения всего дерева:

  1. SELECT node.name, (COUNT(parent.name) - 1) AS depth
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name
  6. ORDER BY node.lft;
  7.  
  8. +----------------------+-------+
  9. | name | depth |
  10. +----------------------+-------+
  11. | ELECTRONICS | 0 |
  12. | TELEVISIONS | 1 |
  13. | TUBE | 2 |
  14. | LCD | 2 |
  15. | PLASMA | 2 |
  16. | PORTABLE ELECTRONICS | 1 |
  17. | MP3 PLAYERS | 2 |
  18. | FLASH | 3 |
  19. | CD PLAYERS | 2 |
  20. | 2 WAY RADIOS | 2 |
  21. +----------------------+-------+

Мы можем использовать значение глубины для формирования отступов с у наших категорий с помощью строковых функций CONCAT и REPEAT
  1. SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name
  6. ORDER BY node.lft;
  7.  
  8. +-----------------------+
  9. | name |
  10. +-----------------------+
  11. | ELECTRONICS |
  12. | TELEVISIONS |
  13. | TUBE |
  14. | LCD |
  15. | PLASMA |
  16. | PORTABLE ELECTRONICS |
  17. | MP3 PLAYERS |
  18. | FLASH |
  19. | CD PLAYERS |
  20. | 2 WAY RADIOS |
  21. +-----------------------+

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

    по мере увеличения размера глубины и уменьшения.

    Глубина поддерева (ветки)

    Когда нам нужна подробная информация о ветке, мы не можем ограничить узел или родительские таблицы в нашем объединении (self-join), потому что это испортит наши результаты. Вместо этого, мы добавим третье объединение, а также подзапрос, чтобы определить глубину, которая будет новой точкой отсчета для нашей ветки:

    1. SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
    2. FROM nested_category AS node,
    3. nested_category AS parent,
    4. nested_category AS sub_parent,
    5. (
    6. SELECT node.name, (COUNT(parent.name) - 1) AS depth
    7. FROM nested_category AS node,
    8. nested_category AS parent
    9. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    10. AND node.name = 'PORTABLE ELECTRONICS'
    11. GROUP BY node.name
    12. ORDER BY node.lft
    13. )AS sub_tree
    14. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    15. AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
    16. AND sub_parent.name = sub_tree.name
    17. GROUP BY node.name
    18. ORDER BY node.lft;
    19.  
    20.  
    21. +----------------------+-------+
    22. | name | depth |
    23. +----------------------+-------+
    24. | PORTABLE ELECTRONICS | 0 |
    25. | MP3 PLAYERS | 1 |
    26. | FLASH | 2 |
    27. | CD PLAYERS | 1 |
    28. | 2 WAY RADIOS | 1 |
    29. +----------------------+-------+

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

    Представьте, что вы показываете категории продуктов электроники на веб-сайте продавца. Когда пользователь щелкает на категории, вы хотите, чтобы отобразились продукты этой категории, а также немедленное были перечислены его подкатегории, но не все дерево категорий под ним. Для этого нам нужно показать, узлы и его непосредственные подузлы, но не ниже по дереву. Например, при показе категории PORTABLE ELECTRONICS, мы хотим показать MP3 PLAYERS, CD PLAYERS и 2 WAY RADIOS, но не FLASH.

    Это можно легко сделать путем добавления предложения HAVING в наших предыдущих запросов:

    1. SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
    2. FROM nested_category AS node,
    3. nested_category AS parent,
    4. nested_category AS sub_parent,
    5. (
    6. SELECT node.name, (COUNT(parent.name) - 1) AS depth
    7. FROM nested_category AS node,
    8. nested_category AS parent
    9. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    10. AND node.name = 'PORTABLE ELECTRONICS'
    11. GROUP BY node.name
    12. ORDER BY node.lft
    13. )AS sub_tree
    14. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    15. AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
    16. AND sub_parent.name = sub_tree.name
    17. GROUP BY node.name
    18. HAVING depth <= 1
    19. ORDER BY node.lft;
    20.  
    21. +----------------------+-------+
    22. | name | depth |
    23. +----------------------+-------+
    24. | PORTABLE ELECTRONICS | 0 |
    25. | MP3 PLAYERS | 1 |
    26. | CD PLAYERS | 1 |
    27. | 2 WAY RADIOS | 1 |
    28. +----------------------+-------+

    Если вы не хотите, чтобы отображался родительский узел, измените HAVING depth <= 1 на HAVING depth = 1.

    Агрегирующие функции во вложенных множествах

    Давайте добавим таблицу продуктов, которые мы можем использовать, чтобы продемонстрировать агрегатныe функции:

    1. CREATE TABLE product(
    2. product_id INT AUTO_INCREMENT PRIMARY KEY,
    3. name VARCHAR(40),
    4. category_id INT NOT NULL
    5. );
    6.  
    7.  
    8. INSERT INTO product(name, category_id) VALUES('20" TV',3),('36" TV',3),
    9. ('Super-LCD 42"',4),('Ultra-Plasma 62"',5),('Value Plasma 38"',5),
    10. ('Power-MP3 5gb',7),('Super-Player 1gb',8),('Porta CD',9),('CD To go!',9),
    11. ('Family Talk 360',10);
    12.  
    13. SELECT * FROM product;
    14.  
    15. +------------+-------------------+-------------+
    16. | product_id | name | category_id |
    17. +------------+-------------------+-------------+
    18. | 1 | 20&quot; TV | 3 |
    19. | 2 | 36&quot; TV | 3 |
    20. | 3 | Super-LCD 42&quot; | 4 |
    21. | 4 | Ultra-Plasma 62&quot; | 5 |
    22. | 5 | Value Plasma 38&quot; | 5 |
    23. | 6 | Power-MP3 128mb | 7 |
    24. | 7 | Super-Shuffle 1gb | 8 |
    25. | 8 | Porta CD | 9 |
    26. | 9 | CD To go! | 9 |
    27. | 10 | Family Talk 360 | 10 |
    28. +------------+-------------------+-------------+

    Теперь давайте выполним запрос, который сможет получить дерево наших категорий, а также количество продуктов по каждой категории:
    1. SELECT parent.name, COUNT(product.name)
    2. FROM nested_category AS node ,
    3. nested_category AS parent,
    4. product
    5. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    6. AND node.category_id = product.category_id
    7. GROUP BY parent.name
    8. ORDER BY node.lft;
    9.  
    10.  
    11. +----------------------+---------------------+
    12. | name | COUNT(product.name) |
    13. +----------------------+---------------------+
    14. | ELECTRONICS | 10 |
    15. | TELEVISIONS | 5 |
    16. | TUBE | 2 |
    17. | LCD | 1 |
    18. | PLASMA | 2 |
    19. | PORTABLE ELECTRONICS | 5 |
    20. | MP3 PLAYERS | 2 |
    21. | FLASH | 1 |
    22. | CD PLAYERS | 2 |
    23. | 2 WAY RADIOS | 1 |
    24. +----------------------+---------------------+

    Это наше типичное целое дерево запроса с добавленными COUNT и GROUP BY, наряду со ссылкой на продукт таблицы и соединением между узлом и продуктами таблицы в предикате WHERE. Как вы видите, есть запись для каждой категории и число подкатегорий содержащихся в родительских категориях.

    Добавление новых узлов

    Теперь, когда мы узнали, как получить наше дерево, мы должны взглянуть на то, как обновить наше дерево путем добавления новых узлов. Давайте посмотрим на нашу схему модели вложенных множеств снова:

    Если мы хотим добавить новый узел между узлами TELEVISIONS и PORTABLE ELECTRONICS, новый узел будет иметь lft и rgt значения 10 и 11, и все его узлы справа будут иметь свои lft и rgt значения увеличена на два. Затем мы добавляем новый узел с соответствующим значениями lft и rgt. Хотя это может быть сделано с помощью хранимых процедур в MySQL 5, я буду считать, что в данный момент большинство читателей используют 4.1, так как это последняя стабильная версия, и я буду изолировать мой запрос с выражением LOCK TABLES:

    1. LOCK TABLE nested_category WRITE;
    2.  
    3.  
    4. SELECT @myRight := rgt FROM nested_category
    5. WHERE name = 'TELEVISIONS';
    6.  
    7.  
    8.  
    9. UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
    10. UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
    11.  
    12. INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);
    13.  
    14. UNLOCK TABLES;

    Мы можем проверить наши вложения с нашими отступом дерева запроса:

    1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
    2. FROM nested_category AS node,
    3. nested_category AS parent
    4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    5. GROUP BY node.name
    6. ORDER BY node.lft;
    7.  
    8.  
    9. +-----------------------+
    10. | name |
    11. +-----------------------+
    12. | ELECTRONICS |
    13. | TELEVISIONS |
    14. | TUBE |
    15. | LCD |
    16. | PLASMA |
    17. | GAME CONSOLES |
    18. | PORTABLE ELECTRONICS |
    19. | MP3 PLAYERS |
    20. | FLASH |
    21. | CD PLAYERS |
    22. | 2 WAY RADIOS |
    23. +-----------------------+

    Если вместо этого мы хотим добавить узел в качестве дочернего узла, который не имеет существующих детей, мы должны немного изменить наши процедуры. Давайте добавим новый узел FRS ниже узла 2 WAY RADIOS:
    1. LOCK TABLE nested_category WRITE;
    2.  
    3. SELECT @myLeft := lft FROM nested_category
    4.  
    5. WHERE name = '2 WAY RADIOS';
    6.  
    7. UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
    8. UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;
    9.  
    10. INSERT INTO nested_category(name, lft, rgt) VALUES('FRS', @myLeft + 1, @myLeft + 2);
    11.  
    12. UNLOCK TABLES;

    Как видите, наш новый узел теперь правильно вложен:
    1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
    2. FROM nested_category AS node,
    3. nested_category AS parent
    4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    5. GROUP BY node.name
    6. ORDER BY node.lft;
    7.  
    8.  
    9. +-----------------------+
    10. | name |
    11. +-----------------------+
    12. | ELECTRONICS |
    13. | TELEVISIONS |
    14. | TUBE |
    15. | LCD |
    16. | PLASMA |
    17. | GAME CONSOLES |
    18. | PORTABLE ELECTRONICS |
    19. | MP3 PLAYERS |
    20. | FLASH |
    21. | CD PLAYERS |
    22. | 2 WAY RADIOS |
    23. | FRS |
    24. +-----------------------+

    Удаление узлов

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

    При удалении листа узла, в отличие от добавления новых узлов, мы удаляем узел и его ширину от каждого узла правее:

    1. LOCK TABLE nested_category WRITE;
    2.  
    3.  
    4. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
    5. FROM nested_category
    6. WHERE name = 'GAME CONSOLES';
    7.  
    8.  
    9. DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
    10.  
    11.  
    12. UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
    13. UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
    14.  
    15. UNLOCK TABLES;

    И опять, мы выполняем запрос оформляя отступы в дереве, чтобы подтвердить что наш узел был удален без нарушения иерархии:

    1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
    2. FROM nested_category AS node,
    3. nested_category AS parent
    4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    5. GROUP BY node.name
    6. ORDER BY node.lft;
    7.  
    8.  
    9. +-----------------------+
    10. | name |
    11. +-----------------------+
    12. | ELECTRONICS |
    13. | TELEVISIONS |
    14. | TUBE |
    15. | LCD |
    16. | PLASMA |
    17. | PORTABLE ELECTRONICS |
    18. | MP3 PLAYERS |
    19. | FLASH |
    20. | CD PLAYERS |
    21. | 2 WAY RADIOS |
    22. | FRS |
    23. +-----------------------+

    Этот подход работает одинаково хорошо при удалении узла и всех его детей:
    1. LOCK TABLE nested_category WRITE;
    2.  
    3.  
    4. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
    5. FROM nested_category
    6. WHERE name = 'MP3 PLAYERS';
    7.  
    8.  
    9. DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
    10.  
    11.  
    12. UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
    13. UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
    14.  
    15. UNLOCK TABLES;

    И опять, мы запрашиваем, чтобы увидеть, успешно ли мы удалили все ветки:
    1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
    2. FROM nested_category AS node,
    3. nested_category AS parent
    4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    5. GROUP BY node.name
    6. ORDER BY node.lft;
    7.  
    8.  
    9. +-----------------------+
    10. | name |
    11. +-----------------------+
    12. | ELECTRONICS |
    13. | TELEVISIONS |
    14. | TUBE |
    15. | LCD |
    16. | PLASMA |
    17. | PORTABLE ELECTRONICS |
    18. | CD PLAYERS |
    19. | 2 WAY RADIOS |
    20. | FRS |
    21. +-----------------------+

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

    1. LOCK TABLE nested_category WRITE;
    2.  
    3.  
    4. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
    5. FROM nested_category
    6. WHERE name = 'PORTABLE ELECTRONICS';
    7.  
    8.  
    9. DELETE FROM nested_category WHERE lft = @myLeft;
    10.  
    11.  
    12. UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
    13. UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
    14. UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
    15.  
    16. UNLOCK TABLES;

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

    1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
    2. FROM nested_category AS node,
    3. nested_category AS parent
    4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
    5. GROUP BY node.name
    6. ORDER BY node.lft;
    7.  
    8.  
    9. +---------------+
    10. | name |
    11. +---------------+
    12. | ELECTRONICS |
    13. | TELEVISIONS |
    14. | TUBE |
    15. | LCD |
    16. | PLASMA |
    17. | CD PLAYERS |
    18. | 2 WAY RADIOS |
    19. | FRS |
    20. +---------------+

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

    Заключительное слово
    Хотя я надеюсь, что информация в данной статье, будет полезна для вас, концепция вложенных множеств в SQL была вокруг в течение более десяти лет, и есть много дополнительной информации, имеющейся в книгах и в интернете. На мой взгляд, наиболее полным источником информации об управлении иерархической информации является книга под названием Деревья Джо Celko и иерархии в SQL для Smarties, написанная очень уважаемым автором в области передовых SQL, Джо Celko. Джо Celko часто приписывают модель вложенных множеств и на сегодняшний день является самым плодовитым автором по этому вопросу. Я нашел книгу Celko, чтобы быть бесценным ресурсом в своих исследованиях и очень рекомендую его. В книге рассматриваются сложные вопросы, которые я не в этой статье, а также предоставляет дополнительные методы для управления иерархическими данными в дополнение к списку смежности и вложенные модели Set.

    В Литература / Ресурсы следующем разделе я перечислил некоторые веб-ресурсы, которые могут быть использованы в исследованиях управления иерархическими данными, в том числе пара PHP соответствующими ресурсами, которые включают встроенные библиотеки PHP для обработки вложенных множеств в MySQL. Те из вас, которые в настоящее время используется модель смежности список и хотел бы, чтобы экспериментировать с моделью вложенных набор будет найти пример кода для преобразования между ними в Хранение иерархических данных в базе данных ресурсов, перечисленных ниже. http://www.sitepoint.com/hierarchical-data-database/