Рекурсивная структура группы в MySQL

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

Здесь, где это становится сложно. Клиент хочет, чтобы группы также содержали группы, произвольную глубину и произвольное перекрытие (группы могут быть в нескольких группах, а группы могут содержать несколько групп). Это достаточно легко хранить (с таблицей group_groups), но трудно запросить без какого-либо расширения, например, Oracle CONNECT BY.

Эта рекурсивная иерархия также должна быть ретроактивной - это означает, что если группа А содержит группу В, а группа В изменена, то группа А также будет изменена - поэтому я не могу обмануть и просто сгладить структуру. Если вы не верите мне, что его нельзя просто сгладить, рассмотрите эту ситуацию. У вас есть группа под названием "классные люди", которая содержит пользователей 1 и 2. Кто-то создает группу под названием "ДЕЙСТВИТЕЛЬНО классные люди", которая содержит пользователя 3 и содержит группу "классные люди". Когда я запрашиваю "ДЕЙСТВИТЕЛЬНО классных людей", я должен сделать вывод, что пользователи 1, 2 и 3 находятся в группе. Теперь скажите, что кто-то решает, что пользователь 2 больше не крутой человек и удаляет пользователя 2 из "крутых людей". После этого момента "ДЕЙСТВИТЕЛЬНО здоровые люди" содержат только пользователей 1 и 3. Если бы я изначально выровнял структуру, я бы не знал, чтобы удалить пользователя 2 из "ДЕЙСТВИТЕЛЬНО здоровых людей", когда я удалил его из "классных людей" ".

Таким образом, тривиальное выравнивание не будет работать в этом сценарии. Другие варианты, которые я рассмотрел:

Выполнение рекурсии в коде.
- Слишком медленно для сложных групп, а также требует, чтобы вы выполняли связанные объединения в памяти, а не в базе данных
Сгладьте структуру в group_users_flattened, но также сохраните таблицу group_groups. Создайте триггер для group_users_flattened в INSERT/UPDATE/DELETE, который перейдет в таблицу group_groups, найдите все группы, которые содержат эту группу, и динамически внесите соответствующие изменения в group_users_flattened.
- Я могу представить, что это работает, но кажется запутанным и подверженным ошибкам, и у меня есть ощущение, что у меня есть то, что я не вижу.

Есть ли другие идеи, которые я не рассматривал?

Ответ 1

Посмотрите мой ответ на Каков наиболее эффективный/элегантный способ разобрать плоскую таблицу в дерево?. Я описываю дизайн, который я называю Таблицей закрытия.

В вашем случае у вас будут таблицы Users и Groups и UserGroupMembers, которые являются таблицей пересечения (многие-ко-многим) между пользователями и группами.

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

CREATE TABLE SubgroupPaths (
  supergroup INT UNSIGNED NOT NULL,
  subgroup   INT UNSIGNED NOT NULL,
  pathlength SMALLINT UNSIGNED NOT NULL DEFAULT 0,
  PRIMARY KEY (supergroup, subgroup),
  FOREIGN KEY (supergroup) REFERENCES Groups(groupid),
  FOREIGN KEY (subgroup) REFERENCES Groups(groupid)
);

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

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

INSERT INTO Groups (groupid, groupname) VALUES
(1, 'REALLY cool people'),
(2, 'slightly cool people'),
(3, 'cool people');

INSERT INTO SubgroupPaths (supergroup, subgroup, pathlength) VALUES
(1,1,0), (2,2,0), (3,3,0), -- every group points to itself
(1,3,1), -- REALLY is parent of cool people
(2,3,1); -- slightly is also parent of cool people

Теперь вы можете получить список всех пользователей, которые должны считаться классными людьми, независимо от того, являются ли они членами крутых людей, слегка крутых людей или ДЕЙСТВИТЕЛЬНО крутых людей. Мы даже можем использовать DISTINCT, если некоторые пользователи связаны с более чем одной из этих групп.

SELECT DISTINCT u.*
FROM SubgroupPaths AS cool
JOIN SubgroupPaths AS supercool ON cool.subgroup=supercool.subgroup
JOIN Groups AS g ON supercool.supergroup = g.groupid
JOIN UserGroupMembers AS m ON m.groupid = g.groupid
JOIN Users AS u ON u.userid = m.userid
WHERE cool.subgroup = 3;

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

Подробнее о таблице закрытия, просмотрите мою книгу SQL Antipatterns: избегайте ошибок программирования баз данных.

Обратите внимание на все это: будьте осторожны в нарушении принципа YAGNI.

Я однажды реализовал базу данных для хранения групп с произвольной глубиной, подобных этой, и весь PHP-код для отображения, отчета и администрирования иерархий. Также мне пришлось клонировать иерархические коллекции, когда они были использованы, потому что иерархию можно было реорганизовать позже, и нам нужно было сохранить исторические данные о том, как использовались элементы в иерархии. Потребовались недели, чтобы закодировать и проверить. И когда все это было сделано, пользователь приложения никогда не хранил ни одну иерархию на одну глубину.

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

Ответ 2

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

http://en.wikipedia.org/wiki/Nested_set_model

https://docs.joomla.org/Using_nested_sets

Drawback Однако вставка новой node (строки) потребует обновления всех строк

Ответ 3

Я бы использовал вложенные наборы. Полная информация здесь:

http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/

Хотя я никогда не использовал это для представления перекрытия.

Ответ 4

У вас есть таблица users_groups (со столбцом для каждой строки, чтобы различать записи для пользователей и записи для групп) и отдельную таблицу с несколькими несколькими соединениями, в которой перечислены все члены user_group_memberships?

Я предполагаю, что для таблицы соединений потребуется ограничение, чтобы столбец групп был как FK в первой таблице, так и тип группы. (Другими словами, если таблица переходов имеет два столбца: member_ID и group_ID, то member_ID может быть ссылкой либо на элемент, либо на группу, тогда как group_ID должен ссылаться только на группу.

Это позволит любому пользователю или группе включать в членство в какой-либо группе, не позволяя любому пользователю или группе быть "членом" пользователя.

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

Ответ 5

Как насчет структуры, такой как

Отношения, такие как действительно крутые люди, связанные с крутыми людьми как "закованные" (и, следовательно, соответствующий каскад), и наоборот, бесплатно.

Ответ 6

Рассматривали ли вы структуру самореференции в таблице групп? Скажем, вы ввели столбец под названием "суперкласс". Подобно ООП, подклассы наследуются от суперклассов. Затем дайте ему столбец идентификатора, так что у вас есть:

[ID | Название группы | Какими бы ни были другие столбцы | суперкласс]

И ограничение внешнего ключа между ID и суперклассом.

Таким образом, скажем, у вас есть группа heffalump, ID = 3. Его суперкласс может быть 1, где идентификатор 1 соответствует имени группы winniethepooh.

Скажите, что Woozle имеет идентификатор 4. Он также может иметь суперкласс 1. Таким образом, он все равно будет находиться под winniethepooh.

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

Извините за сложное объяснение, и я надеюсь, что это поможет!

* edit: Я заметил, что это, по сути, первый пример, приведенный в другой ссылке. В этом случае у меня все из других идей. Извините!

Ответ 7

Я бы рассмотрел использование Common Table Expression (CTE) для рекурсии. По моему опыту, это самый эффективный способ запроса иерархических данных в SQL Server.

Вот ссылка, в которой объясняется, как использовать CTE: http://msdn.microsoft.com/en-us/library/ms190766.aspx

И вот простой пример использования CTE для запроса иерархии. Вам, очевидно, придется настроить код для вашего приложения, но это должно указывать на вас в правильном направлении.

WITH Groups AS
(
   --initialization
   SELECT ParentGroups.GroupID, ParentGroups.GroupName, ParentGroups.ParentGroupID
   FROM ParentGroups
   WHERE ParentGroups.ParentGroupID IS NULL
   UNION ALL
   --recursive execution
   SELECT SubGroups.GroupID, SubGroups.GroupName, SubGroups.ParentGroupID
   FROM Groups SubGroups INNER JOIN Groups ParentGroups 
   ON SubGroups.ParentGroupID = ParentGroups.GroupID
)
SELECT * FROM Groups

Кроме того, вам не нужно иметь таблицу group_groups. Вы можете сохранить всю иерархию в таблице групп, добавив столбец ParentGroupID.