Table design for “Users & Groups” plus “Groups within Groups”

Question

I need to represent users and groups, where groups can be nested within other groups.

(Not my design choice – I am replicating another system and must mimic this behavior. I have no access to its implementation details, only its user documentation.)

Putting a group into other groups creates a hierarchy. The users of one group placed in another group gains the access privileges of both groups. For example, if you place the Executives group in the Accounting group, the users of the Executives group enjoy the privileges of both groups. However, users placed only in the Accounting group benefit from the privileges of that group only. (Admittedly, not a likely realistic business scenario, just a contrived example.)

Something like this ERD diagram, I suppose.

I know how to handle a Many-to-Many relationship of user_ to group_. But I have no idea:

• How to represent the nested group-within-group, where a group may belong to zero, one, or more than one other group.
• How to query “Is this group X in group Y”.
• How to query “Is this user Bob in group X” where “group X may be either directly assigned to that user or inherited via group-within-group”.

Is this group-within-groups considered a “recursive” relationship? What is the correct technical term?

Possibly related: Recursive query in SQL Server and Recursive SQL query to identify

Answer 1

I'd just go straight for a self-referencing key ( adjacency list, hierarchy relationship, recursive relationship, I have no idea what the "most correct and proper" term for it is, but any of these should get the point across to a sufficiently tuned-in audience ) on what would effectively be a "principal" or "role" table, along with a membership table. While I'd draw my inspiration from SQL Server, PostgreSQL also does this for it's own security management, like what is shown through \du or \dg. That said, there may even be value in considering trying to handle all of this with the built-in security management:

CREATE ROLE accounting;
GRANT SELECT ON account TO accounting;
CREATE ROLE executives;
GRANT accounting TO executives;
CREATE USER cto_bill;
GRANT executives TO cto_bill;

"CTO Bill" should now be able to SELECT from the account table, via the executives role through to the accounting role, all completely out of the box. If an application needs to know the chained permissions, they could be exposed via \du or some form of query against the pg_catalog's pg_auth_members and pg_roles tables:

SELECT  r.rolname, r.rolsuper, r.rolinherit,
        r.rolcreaterole, r.rolcreatedb, r.rolcanlogin,
        r.rolconnlimit, ARRAY(  SELECT  b.rolname
                                FROM    pg_catalog.pg_auth_members m
                                INNER JOIN pg_catalog.pg_roles b 
                                    ON  ( m.roleid = b.oid )
                                WHERE   m.member = r.oid ) as memberof
FROM    pg_catalog.pg_roles r
WHERE   r.rolcanlogin = 'f'
ORDER BY 1;

If a total nuts-and-bolts solution is deemed necessary, you could build a schema similar to this:

CREATE TABLE Principal
(
    Principal_PK             SERIAL NOT NULL,
    Name                     VARCHAR( 128 ) NOT NULL,
    PasswordHash             BYTEA,
    Type                     CHAR( 1 ) NOT NULL
);

ALTER TABLE Principal
ADD CONSTRAINT PK__Principal
    PRIMARY KEY ( Principal_PK );

ALTER TABLE Principal
ADD CONSTRAINT UQ__Principal__Name
    UNIQUE ( Name );

ALTER TABLE Principal
ADD CONSTRAINT CK__Principal__Type
    CHECK ( Type IN ( 'U', 'G' ) );

CREATE TABLE PrincipalMembership
(
    PrincipalMembership_PK   SERIAL NOT NULL,
    Principal_FK             INTEGER NOT NULL,
    IsMemberOfPrincipal_FK   INTEGER NOT NULL,
    DateCreated              TIMESTAMP NOT NULL
);

ALTER TABLE PrincipalMembership
ADD CONSTRAINT PK__PrincipalMembership
    PRIMARY KEY ( PrincipalMembership_PK );

ALTER TABLE PrincipalMembership
ADD CONSTRAINT FK__PrincipalMembership__Principal
    FOREIGN KEY ( Principal_FK )
    REFERENCES Principal ( Principal_PK );

ALTER TABLE PrincipalMembership
ADD CONSTRAINT FK__PrincipalMembership__IsMemberOfPrincipal
    FOREIGN KEY ( IsMemberOfPrincipal_FK )
    REFERENCES Principal ( Principal_PK );

ALTER TABLE PrincipalMembership
ADD CONSTRAINT UQ__PrincipalMembership__Principal__IsMemberOfPrincipal
    UNIQUE ( Principal_FK, IsMemberOfPrincipal_FK );

ALTER TABLE PrincipalMembership
ALTER COLUMN DateCreated SET DEFAULT ( NOW() );

INSERT  INTO Principal ( Name, PasswordHash, Type )
VALUES  ( 'accounting', NULL, 'G' ),
        ( 'executives', NULL, 'G' ),
        ( 'cto_bill', E'\\x00', 'U' );

INSERT  INTO PrincipalMembership ( Principal_FK, IsMemberOfPrincipal_FK )
SELECT  p.Principal_PK, m.Principal_PK
FROM (      SELECT  'executives', 'accounting'
UNION ALL   SELECT  'cto_bill', 'executives' ) pl ( Name, IsMemberOf )
INNER JOIN Principal p
    ON  p.Name = pl.Name
INNER JOIN Principal m
    ON  m.Name = pl.IsMemberOf;

Then use pretty much any tree-traversing method you'd like, such as a Recursive CTE, to determine various membership properties:

;WITH RECURSIVE cte_Membership AS (
    SELECT  p.Principal_PK, p.Name, pm.IsMemberOfPrincipal_FK
    FROM    Principal p
    LEFT JOIN PrincipalMembership pm
        ON  pm.Principal_FK = p.Principal_PK
    UNION ALL
    SELECT  c.Principal_PK, c.Name, pm.IsMemberOfPrincipal_FK
    FROM    cte_Membership c
    INNER JOIN Principal p
        ON  p.Principal_PK = c.IsMemberOfPrincipal_FK
    INNER JOIN PrincipalMembership pm
        ON  pm.Principal_FK = p.Principal_PK )
SELECT  m.Name, p.Name AS IsMemberOf
FROM    cte_Membership m
LEFT JOIN Principal p
    ON  p.Principal_PK = m.IsMemberOfPrincipal_FK
ORDER BY m.Name, IsMemberOf;

Edit: It's probably very much worth mentioning that management of solutions involving self-referencing keys and recursive traversals can go tits up in a hurry if caution isn't taken to ensure no cyclic references are made. If somebody were to "accidentally" make accounting a member of the executives group, the sample CTE would no longer function, and as the complexity of the hierarchy increases, so to does the likelihood of such an error. Safeguarding against cyclic references is a bit of a pain in the ass, frankly, but hiding CRUD operations against these tables in stored procedures can help immensely in cases like this one. Since you're attempting to replicate a preexisting solution, perhaps there's some guidelines in that system which can assist in developing a suitable litmus test for the new one.

Answer 2

First off - are you sure the group_ self-relationship is one-to-many? It seems to me that Executives should not only be a member of Accounting but also of Penthouse Restaurant. Similarly Accounting not only contains Executives but also Trolls. This would be many-to-many, and you've already solved that problem for user/ group interaction. Solve it the same way here.

If you're absolutely certain it's one-to-many there are several different implementation of trees in SQL.