Un problème intéressant. Voici une solution pour autant que le nombre de rôles dans votre système soit inférieur à 128. (Tout nombre supérieur à 128 rôles distincts entraînera la création de BITAND à l'échec).
L'approche repose sur la création d'un jeu de pouvoirs ("P") de votre ensemble de rôles et sur la recherche de l'ensemble ("Q") contenant des membres de "P" qui couvrent tous les utilisateurs. Il s'agit ensuite de trouver les membres de "Q" ayant le moins de rôles distincts.
Aucune promesse de performance n'est faite ici. Il s'agit d'une approche de force brute, mais les problèmes de type combinaison nécessitent souvent une force brute.
with user_role_data (USER_ID, ROLE_ID) AS (
SELECT 'user1','role1' FROM DUAL UNION ALL
SELECT 'user1','role2' FROM DUAL UNION ALL
SELECT 'user1','role3' FROM DUAL UNION ALL
SELECT 'user2','role1' FROM DUAL UNION ALL
SELECT 'user2','role4' FROM DUAL UNION ALL
SELECT 'user3','role2' FROM DUAL UNION ALL
SELECT 'user3','role6' FROM DUAL UNION ALL
SELECT 'user3','role5' FROM DUAL UNION ALL
SELECT 'user4','role1' FROM DUAL )
-- End of sample data
,
distinct_roles as ( SELECT distinct role_id FROM user_role_data ORDER BY role_id),
numbered_roles as ( SELECT power(2, rownum-1) role_ps_id, role_id FROM distinct_roles),
-- There will be 2**n entries in the powerset, where n = the number of distinct roles
ps_driver as ( SELECT rownum-1 ps_id FROM DUAL connect by ROWNUM <= power(2, ( SELECT count(*) FROM distinct_roles))),
-- Create a powerset of all the roles.
powerset as (
SELECT psd.ps_id, r.role_id
FROM ps_driver psd
CROSS APPLY ( SELECT nr.role_id
FROM numbered_roles nr
-- Note: this bit requires that the # of roles be less than 128.
WHERE bitand(nr.role_ps_id, psd.ps_id) > 0 ) r ),
-- Build a summary of each power set, just for display purposes
powerset_summary as (
SELECT ps_id,
listagg(role_id,',') within group ( order by role_id ) role_list
FROM powerset
GROUP BY ps_id ),
-- Get the sets the cover 100% of the users and the size and contents of each set
ps_users as (
SELECT ps.ps_id,
count(distinct urd.user_id) covered_users,
count(distinct ps.role_id) required_roles,
( SELECT role_list FROM powerset_summary pss WHERE pss.ps_id = ps.ps_id ) role_list
FROM powerset ps
INNER JOIN user_role_data urd ON urd.role_id = ps.role_id
GROUP BY ps.ps_id
HAVING count(distinct urd.user_id) = ( SELECT count(distinct urd2.user_id) from user_role_data urd2 )
)
-- List the sets that cover all the users with the fewest number of roles
select * from ps_users
order by required_roles
fetch first 1 row with ties;
+-------+---------------+----------------+-------------+
| PS_ID | COVERED_USERS | REQUIRED_ROLES | ROLE_LIST |
+-------+---------------+----------------+-------------+
| 3 | 4 | 2 | role1,role2 |
| 33 | 4 | 2 | role1,role6 |
| 17 | 4 | 2 | role1,role5 |
+-------+---------------+----------------+-------------+
Version compatible avec Oracle 11.2
with user_role_data (USER_ID, ROLE_ID) AS (
SELECT 'user1','role1' FROM DUAL UNION ALL
SELECT 'user1','role2' FROM DUAL UNION ALL
SELECT 'user1','role3' FROM DUAL UNION ALL
SELECT 'user2','role1' FROM DUAL UNION ALL
SELECT 'user2','role4' FROM DUAL UNION ALL
SELECT 'user3','role2' FROM DUAL UNION ALL
SELECT 'user3','role6' FROM DUAL UNION ALL
SELECT 'user3','role5' FROM DUAL UNION ALL
SELECT 'user4','role1' FROM DUAL )
-- End of sample data
,
distinct_roles as ( SELECT distinct role_id FROM user_role_data ORDER BY role_id),
numbered_roles as ( SELECT power(2, rownum-1) role_ps_id, role_id FROM distinct_roles),
-- There will be 2**n entries in the powerset, where n = the number of distinct roles
ps_driver as ( SELECT rownum-1 ps_id FROM DUAL connect by ROWNUM <= power(2, ( SELECT count(*) FROM distinct_roles))),
-- Create a powerset of all the roles.
powerset as (
SELECT psd.ps_id, nr.role_id
FROM ps_driver psd
CROSS JOIN numbered_roles nr
WHERE bitand(nr.role_ps_id, psd.ps_id) > 0 ),
-- Build a summary of each power set, just for display purposes
powerset_summary as (
SELECT ps_id,
listagg(role_id,',') within group ( order by role_id ) role_list
FROM powerset
GROUP BY ps_id ),
-- Get the sets the cover 100% of the users and the size and contents of each set
ps_users as (
SELECT ps.ps_id,
count(distinct urd.user_id) covered_users,
count(distinct ps.role_id) required_roles,
( SELECT role_list FROM powerset_summary pss WHERE pss.ps_id = ps.ps_id ) role_list,
dense_rank() over ( order by count(distinct ps.role_id)) result_number
FROM powerset ps
INNER JOIN user_role_data urd ON urd.role_id = ps.role_id
GROUP BY ps.ps_id
HAVING count(distinct urd.user_id) = ( SELECT count(distinct urd2.user_id) from user_role_data urd2 )
)
select * from ps_users
where result_number = 1
order by required_roles;
