Recursive group structure in MySQL

Question

I am developing a system which needs to allow users to be placed into groups. These groups can be freely created, edited, and deleted by other privileged users in the system. That part is easy; just create a group_users table that links users into groups. (If you're a stickler for normalization then you may create a group table that just lists off groups and then have a group_users table that links them together -- that's fine too)

Here's where it gets tricky. The client wants groups to also contain groups, to arbitrary depth and with arbitrary overlap (groups can be in multiple groups, and groups can contain multiple groups). That's easy enough to store (with a group_groups table), but it's difficult to query against without some sort extension like Oracle's CONNECT BY.

This recursive hierarchy also needs to be retroactive -- meaning that if group A contains group B, and group B is modified, then group A will be modified too -- so I can't cheat and just flatten out the structure. If you don't believe me that it can't simply be flattened, consider this situation. You have a group called "cool people" which contains users 1 and 2. Someone creates a group called "REALLY cool people" which contains user 3 and contains the group "cool people". When I query against "REALLY cool people" I should conclude that users 1, 2, and 3 are in the group. Now say that someone decides that user 2 isn't a cool person anymore and removes user 2 from "cool people". After that point in time, "REALLY cool people" only contains users 1 and 3. If I had originally flattened out the structure, I wouldn't know to remove user 2 from "REALLY cool people" when I removed him from "cool people".

So a trivial flattening won't work in this scenario. Other options I've considered:

• Doing the recursion in code.
  • Too slow for complex groups, and also requires you to then do related joins in memory rather than on the database
• Flatten the structure out into group_users_flattened, but also maintain a group_groups table. Create a trigger for group_users_flattened on INSERT/UPDATE/DELETE that will go to the group_groups table, find all groups that contain this group, and dynamically make the appropriate changes to group_users_flattened.
  • I can imagine this working, but it seems convoluted and error-prone, and I have a feeling there's a gotcha that I'm not seeing.

Are there other ideas that I haven't considered?

Answer 1

See my answer to What is the most efficient/elegant way to parse a flat table into a tree?. I describe a design I call Closure Table.

In your case, you'd have your tables Users and Groups and UserGroupMembers that is the intersection table (many-to-many) between Users and Groups.

Then you'd need another table to describe how groups are nested. Call it SubgroupPaths for instance. This records every path relating a given group to its subgroups.

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)
);

You may also need some permutations of compound indexes to support certain queries you'd run against this table.

This design allows you to have multiple hierarchies, so you could have group "cool people" be a descendant of each of its supergroups.

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

Now you can get the list of all users who should be considered cool people, regardless of whether they are members of cool people, slightly cool people, or REALLY cool people. We can even throw in a DISTINCT in case some users are associated with more than one of these groups.

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;

I prefer Closure Table over the Nested Sets design suggested by other answers, because Closure Table supports referential integrity constraints, and there are some queries that are hard in Nested Sets but easier in Closure Table.

For more on Closure Table, check out my book SQL Antipatterns Volume 1: Avoiding the Pitfalls of Database Programming.

---

Footnote to all this: be careful about violating the YAGNI principle.

I once implemented a database to store arbitrary-depth groups like this, and all the PHP code to display, report, and administer hierarchies. Also I had to clone hierarchical collections when they were used, because the hierarchy could be reorganized later, and we needed to keep historical data of how the elements in the hierarchy were used. It took weeks to code and test. And when it was all done, the user of the application never actually stored any hierarchy more one one level deep.

Some decision-makers will change their minds about the scope of requirements if you tell them how much work (i.e. budget) it will take to implement and test.

Answer 2

"Queries using nested sets can be expected to be faster than queries using a stored procedure to traverse an adjacency list, and so are the faster option for databases which lack native recursive query constructs, such as MySQL."

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

https://docs.joomla.org/Using_nested_sets

Drawback However inserting a new node (row) will require all rows to be updated accordingly

Answer 3

I'd use nested sets. Full details here:

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

Although I've never used that to represent overlapping.

Answer 4

Could you have a table of users_groups (with a column for each row to distinguish between entries for users and entries for groups) and a separate multi-multi junction table listing all of the user_group_memberships?

I'm guessing that the junction table would need a constraint to ensure that the groups column is both an FK into the first table and that the type is of group. (In other words if the junction table has two columns: member_ID and group_ID then member_ID can be a reference to either a member or a group while group_ID must refer only to a group.

That would allow any user or group to be including in the membership of any group while preventing any user or group from being a "member" of a user.

(BTW: I'm not sufficiently well-versed in MySQL to cook up a working example right now; but I'd like to see one if this suggestion is feasible).

Answer 5

What about a structure such as

A relationship such as really cool people being related to cool people as 'chained' (and thus the appropriate cascade), and vice-versa for free.

Answer 6

Have you considered a self-referential structure in your groups table? Say you put in a column called "superclass." Just like OOP, subclasses inherit from superclasses. Then give it an ID column, so that you have:

[ ID | Group name | Whatever other columns | superclass ]

And a foreign key constraint between ID and superclass.

This way, say you have group heffalump, ID = 3. Its superclass could be 1, where ID of 1 corresponds to group name winniethepooh.

Say Woozle has ID of 4. It can also have superclass 1. So it would still be under winniethepooh.

Fairly simple, but it should work without much trouble. This way, as per your example, "really cool people" would be hierarchical under "cool people," so that the only people in "really cool people" who are NOT in "cool people" would be those that aren't already in "cool people" to begin with. So if you take a person out of "cool people" he wouldn't be under "really cool people," but if you take a person out of "really cool people" it won't affect "cool people."

Sorry about the complicated explanation, and I hope this helps!

*edit: I notice this is essentially the first example given in the other link. In that case, I'm all out of other ideas. Sorry!

Answer 7

I would look into using a Common Table Expression (CTE) for recursion. In my experience, it is the most efficient way to query hierarchical data in SQL Server.

Here is a link which explains how to use CTEs: http://msdn.microsoft.com/en-us/library/ms190766.aspx

And here is a simple example of how to use a CTE to query a hierarchy. You will obviously have to adjust the code for your application, but this should point you in the right direction.

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

Also, you shouldn't need to have a group_groups table. You can hold the entire hierarchy in the group table by adding a ParentGroupID column.