我有Oracle 11.2 DB和一个有趣的问题。
我碰巧有一张桌子像
USER_ID ROLE_ID
user1 role1
user1 role2
user1 role3
user2 role1
user2 role4
user3 role2
user3 role6
user3 role5
user4 role1
我的目标是获取最少数量的角色,以覆盖所有用户。在这种情况下,应为role1 + role2
我的想法是我应该:
获取所有可用的组合,例如
第一个用户的第一个角色+第二个用户的
第一个角色+ ....第n个用户的第一个角色第一个用户的第一个角色+第二个用户的第一个角色+ ....第n个用户的第二个角色
....
第一个用户的第一个角色用户+第二个用户的第n个角色+ ....第n个用户的第n个角色,
因此我得到了所有可能的组合
我需要从所有行中删除重复项
删除重复项后,我需要使行的分隔符的长度/最少最少
问题是我不知道如何获得所有可能的角色组合。我尝试使用“按级别连接”进行实验,但是并没有达到我的期望。
有人可以帮忙吗?
有趣的问题。只要系统中的角色数量少于128个,就可以采用这种方法。(任何大于128个不同的角色都将导致BITAND
失败)。
该方法依赖于对一组角色进行幂集(“ P”),然后找到包含“ P”成员且覆盖所有用户的组(“ Q”)。然后,找到具有最少不同角色的“ Q”成员。
这里没有性能保证。这是一种蛮力方法,但是组合型问题通常需要蛮力。
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 | +-------+---------------+----------------+-------------+
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;
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句