MySQL中的递归组结构

Question

我正在开发一个系统,需要允许用户被分组.这些组可以由系统中的其他特权用户自由创建,编辑和删除.那部分很容易; 只需创建一个group_users将用户链接到组的表.(如果你是规范化的坚持者,那么你可以创建一个group只列出组的group_users表,然后有一个表将它们链接在一起 - 这也很好)

这是它变得棘手的地方.客户端希望组还包含任意深度和任意重叠的组(组可以在多个组中,组可以包含多个组).这很容易存储(使用group_groups表),但如果没有像Oracle的CONNECT BY这样的排序扩展,很难查询.

这个递归层次结构也需要追溯 - 意味着如果组A包含组B,组B被修改,那么组A也将被修改 - 所以我不能作弊并且只是扁平化结构.如果你不相信我,它不能简单地被夷为平地,请考虑这种情况.你有一个名为"酷人"的小组,其中包含用户1和2.有人创建了一个名为"真正很酷的人"的小组,其中包含用户3并包含"酷人"组.当我查询"真的很酷的人"时,我应该得出结论,用户1,2和3都在群组中.现在说有人决定用户2不再是一个很酷的人,并从"酷人"中删除用户2.在那个时间点之后,"真正很酷的人"只包含用户1和3.如果我最初将结构弄平,当我将他从"酷人"中删除时,我不知道将用户2从"真正的酷人"中删除".

因此,在这种情况下,一个微不足道的扁平化将不起作用.我考虑过的其他选择:

• 在代码中进行递归.
  • 复杂组太慢,并且还要求您在内存中而不是在数据库上执行相关联接
• 将结构展平成group_users_flattened,但也保持一张group_groups桌子.为group_users_flattenedINSERT/UPDATE/DELETE 创建一个触发器,该触发器将转到该group_groups表,查找包含该组的所有组,并动态地进行相应的更改group_users_flattened.
  • 我可以想象这是有效的,但它似乎令人费解并且容易出错,而且我感觉有一种我没有看到的问题.

还有其他我未考虑过的想法吗？

Answer 1

请参阅我对将平面表解析为树的最有效/优雅的方法是什么？。我描述了一种称为Closure Table 的设计。

在您的情况下，您将拥有表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 的更多信息，请参阅我的书《SQL Antipatterns Volume 1：Avoiding the Pitfalls of Database Programming》。

所有这些的脚注：小心违反YAGNI原则。

我曾经实现过一个数据库来存储像这样的任意深度组，以及用于显示、报告和管理层次结构的所有 PHP 代码。此外，我还必须在使用层次结构集合时克隆它们，因为层次结构可以稍后重新组织，并且我们需要保留层次结构中元素的使用方式的历史数据。编码和测试花了几周时间。当这一切完成后，应用程序的用户实际上从未存储过更深一层的任何层次结构。

如果您告诉一些决策者实施和测试需要多少工作（即预算），他们就会改变对需求范围的看法。