Recursive group structure in MySQL

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 coolJOIN SubgroupPaths AS supercool ON cool.subgroup=supercool.subgroupJOIN Groups AS g ON supercool.supergroup = g.groupidJOIN UserGroupMembers AS m ON m.groupid = g.groupidJOIN Users AS u ON u.userid = m.useridWHERE 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: 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.

"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

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

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.