oracle sql多重分组

Fhntvbq Sfdhfyfyfh

我有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

我的想法是我应该:

  1. 获取所有可用的组合,例如

    第一个用户的第一个角色+第二个用户的
    第一个角色+ ....第n个用户的第一个角色第一个用户的第一个角色+第二个用户的第一个角色+ ....第n个用户的第二个角色
    ....
    第一个用户的第一个角色用户+第二个用户的第n个角色+ ....第n个用户的第n个角色,
    因此我得到了所有可能的组合

  2. 我需要从所有行中删除重复项

  3. 删除重复项后,我需要使行的分隔符的长度/最少最少

问题是我不知道如何获得所有可能的角色组合。我尝试使用“按级别连接”进行实验,但是并没有达到我的期望。

有人可以帮忙吗?

马修·麦克佩克(Matthew McPeak)

有趣的问题。只要系统中的角色数量少于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 |
+-------+---------------+----------------+-------------+

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;

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章