Знакомство с вложенными множествами: часть первая

Проблема, которую мы пытаемся решить

Реляционные базы данных отлично подходят для хранения классических родительско-дочерних отношений. Возьмем пример континентов:

continent
id    name
1     Europe
2     America

и страны:

country
id    name              continent_id
1     France            1
2     United Kingdom    1
3     Sweden            1
4     Canada            2

Каждый country принадлежит указанному continent (давайте просто представим, что в этом примере все так просто!), указанному его id в поле continent_id. Запрос на получение сведений для данного country прост:

SELECT
    continent.name AS continent,
    country.name AS country
FROM
    continent,
    country
WHERE
        country.continent_id = continent.id
    AND country.id = '2';

и производит вывод:

+-----------+----------------+
| continent | country        |
+-----------+----------------+
| Europe    | United Kingdom |
+-----------+----------------+
1 row in set (0.00 sec)

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

Наивное решение

Подход по умолчанию может состоять в том, чтобы обобщить и сохранить идентификатор «места» как ссылку на родителя места:

place
id    name              parent_place
1     Europe            NULL
2     France            1
3     United Kingdom    1
4     England           3
5     Wales             3
6     Sweden            1

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

SELECT
    p1.name AS place1,
    p2.name AS place2,
    p3.name AS place3
FROM
    place p1,
    place p2,
    place p3
WHERE
    p1.id = '4'
AND p2.id = p1.parent_place
AND p3.id = p2.parent_place;

И получаем такие результаты, как:

+---------+----------------+--------+
| place1  | place2         | place3 |
+---------+----------------+--------+
| England | United Kingdom | Europe |
+---------+----------------+--------+
1 row in set (0.00 sec)

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

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

Все, что мы действительно сделали с этим подходом, — это запихнули все в одну таблицу, фактически не решив исходную проблему. Как мы можем представить общую иерархию с неограниченной глубиной и при этом сделать данные доступными?

Введите «вложенные наборы».

Вложенные наборы

Вложенные наборы решают именно эту проблему — и даже приносят с собой бонусы! Вот настройка:

location
id    name              lft    rgt
1     Europe            1      14
2     France            2      3
3     United Kingdom    4      11
4     England           5      6
5     Wales             7      8
6     Scotland          9      10
7     Sweden            12     13

Во-первых, очень важно отметить, что введенные нами два столбца — lft и rgt — не ссылаются на другие столбцы location. На самом деле они означают «лево» и «право», и все они (ну, в основном) нужны нам для хранения полной, неограниченной иерархии и для ответа на такие вопросы, как:

  1. Кто мои предки?
  2. Какие мои потомки?
  3. Каковы мои братья и сестры, по порядку?

каждый с одним простым запросом. Звучит слишком просто, верно — как нам удалось упаковать всю эту информацию, добавив всего один столбец? Оказывается, все дело в свойствах lft и rgt и в том, как мы поддерживаем эти свойства при обновлении данных.

Взгляните на следующую диаграмму, которая представляет данные из предыдущей таблицы:

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

  • Если элемент не имеет родителя (например, Европа), его значение lft равно 1.
  • Если элемент является первым дочерним элементом (например, Англия), его значение lft равно значению lft родителя + 1.
  • Если элемент не является первым дочерним элементом (например, Швеция), его значение lft совпадает с rgt значением + 1 предыдущего родственного элемента.
  • Если у элемента есть дочерние элементы (например, Соединенное Королевство), его значение rgt равно значению rgt последнего дочернего элемента + 1.
  • Если у элемента нет дочерних элементов (например, Франция), его значение rgt является его собственным значением lft + 1.

Вы можете думать о каждой записи как о ящике, «содержащем» всех своих потомков — по порядку — и «содержащемся внутри» всех своих предков. Отсюда «вложенные множества».

Оказывается, эти свойства даже позволяют нам тривиально ответить на такой вопрос, как «Сколько у меня потомков?» — оказывается, этот вопрос не особенно полезен, но интересно, что мы можем ответить на него, учитывая, что ответ был бы непостижим, используя представленный ранее наивный подход.

Интересно, что на самом деле мы не можем легко ответить на такие вопросы, как «сколько у меня детей?» или даже «кто мои дети?», но со временем мы решим этот вопрос (не волнуйтесь, это легко исправить!). А пока давайте посмотрим, как мы можем ответить на первоначальные вопросы, на которые мы обещали.

Кто мои предки?

Если вы посмотрите на приведенную выше диаграмму и возьмете Уэльс в качестве примера, должно быть очевидно, что вы можете ответить на этот вопрос концептуально, «посмотрев вверх» и выбрав location, которые «содержат» Уэльс. Другими словами, те, у кого lft меньше, чем lft в Уэльсе, и те, у кого rgt больше, чем rgt в Уэльсе:

SELECT
    ancestor.id,
    ancestor.name
FROM
    location ancestor,
    location original
WHERE
    original.lft > ancestor.lft
AND original.rgt < ancestor.rgt
AND original.id = 5;

Это дает результат:

+----+----------------+
| id | name           |
+----+----------------+
|  1 | Europe         |
|  3 | United Kingdom |
+----+----------------+
2 rows in set (0.00 sec)

Какие мои потомки?

Точно в противоположном направлении потомки «содержатся внутри» местоположения, поэтому их значения lft и rgt должны быть между значениями исходного местоположения. Чтобы получить всех потомков Европы:

SELECT
    descendant.id,
    descendant.name
FROM
    location descendant,
    location original
WHERE
    original.lft < descendant.lft
AND original.rgt > descendant.rgt
AND original.id = 1;

что дает нам:

+----+----------------+
| id | name           |
+----+----------------+
|  2 | France         |
|  3 | United Kingdom |
|  4 | England        |
|  5 | Wales          |
|  6 | Scotland       |
|  7 | Sweden         |
+----+----------------+
6 rows in set (0.00 sec)

Сколько у меня потомков?

Мы даже можем ответить на этот необычный вопрос еще более необычным запросом:

SELECT
    (location.rgt - location.lft - 1) DIV 2 AS num_descendants
FROM
    location
WHERE
    location.id = 3;

Этот запрос дает результат:

+-----------------+
| num_descendants |
+-----------------+
|               3 |
+-----------------+
1 row in set (0.00 sec)

Метод работает, потому что «ширина» записи напрямую связана с количеством записей, которые помещаются «внутри» ее, то есть ее потомков.

Следовать за

Эта статья была довольно длинной, и хотя есть еще что рассказать, я не хочу перегружать информацией на данном этапе. Оставайтесь с нами для второй части, которая будет доступна в ближайшее время; он будет охватывать вопрос «кто мои дети» и как поддерживать актуальность всех этих значений lft и rgt при обновлении таблицы.

Вспомогательный код для MySQL доступен в репозитории nested-sets-part-one на GitHub. Вся настройка таблицы содержится в setup.sql, а каждый запрос в этой статье содержится в отдельном файле. См. README, если вы не знаете, как его запустить.