Minimal number of groups necessary to cover user/product permissions

Question

I have a list of 365 customers. Each of them has a potentially unique list of products they are allowed to order, up to 18 out of 24 total products (at present). I would like to use groups to assign the permissions. How can I determine the minimum number of unique permission sets?

I have a hunch the answer involves relational division, but I'm still very fuzzy on how that works.

To clarify: I am not just interested in which users have exactly the same permissions. I want to find groups I can use, each user potentially a member of multiple groups, that can reproduce the permissions. For instance, group "A" might have permission to 99498; group "B" have permission to 99507, 99508, 99512. All three users in the truncated data below would be members of "A", and only the first two would be members of "B".

CREATE TABLE UsersProducts (
    [User] INTEGER NOT NULL, 
    [Product] INTEGER NOT NULL, 
    PRIMARY KEY ([User],[Product])
)
CREATE TABLE GroupsProducts (
  [Group] INTEGER NOT NULL,
  [Product] INTEGER NOT NULL,
  PRIMARY KEY ([Group],[Product])
)
CREATE TABLE GroupsUsers (
  [Group] INTEGER NOT NULL,
  [User] INTEGER NOT NULL,
  PRIMARY KEY ([Group],[User])
)

-- Given this UsersProducts information, I want 
--the GroupsProducts and GroupsUsers tables filled.

INSERT UsersProducts
        ( [User],[Product] )
VALUES  (11804,99498),
(11804,99506),
(11804,99507),
(11804,99508),
(11804,99512),
(11804,99547),
(11804,99592),
(11804,99594),
(11804,99647),
(11804,99658),
(11804,99660),
(11804,99667),
(11804,99694),
(11804,99700),
(11804,99771),
(11947,99498),
(11947,99506),
(11947,99507),
(11947,99508),
(11947,99512),
(11947,99547),
(11947,99592),
(11947,99594),
(11947,99647),
(11947,99658),
(11947,99660),
(11947,99667),
(11947,99700),
(11947,99720),
(11947,99771),
(12009,99498),
(12009,99506),
(12009,99507),
(12009,99508),
(12009,99512),
(12009,99547),
(12009,99575),
(12009,99592),
(12009,99594),
(12009,99596),
(12009,99647),
(12009,99658),
(12009,99660),
(12009,99667),
(12009,99694),
(12009,99700),
(12009,99720),
(12009,99771),
(12353,99498),
(12353,99512),
(12353,99547),
(12353,99575),
(12353,99592),
(12353,99594),
(12353,99596),
(12353,99647),
(12353,99658),
(12353,99660),
(12353,99667),
(12353,99694)
-- etc. 365 distinct users, 28 distinct products. 4012 pairings.

Antependium

If this is security/permissions related, then shouldn't the security group permissions already be pre-defined as far as what products should be allowed in each group? If you are auto-generating the security groups based on what products user have ordered in the past, then how are you going to manage those security groups going forward? – Candidacandidacy

en.wikipedia.org/wiki/Set_cover_problem – Endpaper

The crux of this question is set theory, not SQL. Is a "close, but possibly not optimal" answer good enough for your purposes? If so, a straightforward greedy algorithm would probably be the easiest. – Endpaper

@Anon: Close but nonoptimal is definitely good enough. Thanks for the link. – Antependium

BateTech: A client wants to use our storefront system. We have an import operation, using an Excel sheet, that allows you to define up to five groups per user. She insisted she needed 18 groups per user, since some users needed access to 18 products. Once the user/group association is done, the permissions can be set. Future management? That's her problem in the future. :) We're trying to dissuade her from going down this path, but we have to react to what she says she needs. – Antependium

These seems even harder than the set-cover problem, because you have to ensure that no extra products are assigned to a user. Consider two users, one with 19 products and one with 18 products, where the 19 products are the 18 plus one other. The two customers could not use the same groups, although there might be overlap. I don't see the advantage to using groups for this at all. Just give each customer access to the products that s/he/it has. – Cuckoo

Access to products is set at the group level in our system (there are no user ACLs). The client came up with the idea of creating a group for each product. The only difficulty is the number of groups allowed to be put in the import spreadsheet. We'll bypass the import spreadsheet this time. – Antependium

@GordonLinoff -- the two customers could share group A with access to 18 products, and the second user also be a member of group B for the 19th product. It's the difficulty of computing the minimal set of groups to cover the situation that prompted my question. And it's really not worth the time anymore. This is a one time user import; and it is subject to change in the future which could make the hypothetical minimum groups no longer adequate. – Antependium

Answer 1

Thanks to Anon and Gordon Linoff, and much googling on my own: this is an example of the set-cover problem, or perhaps even more difficult, and solving this is just not worth it. We will go with the 24 groups solution with some users being a member of 18 groups at a time. This is known to be far from minimal but it will work and that's all we need. Only the input phase requires care.

Antependium