Oracle 查找所有完全连接的子图

嗨，团队，

with   data ( p1 , p2 ) as 
( select 'a' ,'b' from dual union all
  select 'a' ,'c' from dual union all
  select 'a' ,'d' from dual union all

  select 'b' ,'c' from dual union all
  select 'b' ,'d' from dual union all

  select 'c' ,'d' from dual union all
  select 'c' ,'e' from dual union all
  select 'c' ,'f' from dual union all

  select 'd' ,'e' from dual union all

  select 'e' ,'f' from dual 
)
select * from data ;
复制

我的数据就像上面一样。

假设这些列数据只不过是人员信息。这两列之间的关系是相互知道的 (a知道b，b知道a，即双向)。

有了这些数据，我想找出基于以下条件的组。
1) 每组必须包含2人以上。
2) 一个人应该知道，其余的人在同一组中。


预期o/p为:
-----------------

(甲、乙、丙)
(甲、乙、丙、丁)
(乙、丙、丁)
(c、d、e)

我错过了在上一篇文章中添加以下o/p

(c、e、f)
(a、c、d)
(甲、乙、丁)

一个有趣的问题!

我在Twitter上寻求解决方案。您可以在以下实时SQL脚本中找到社区答案:

https://livesql.oracle.com/apex/livesql/file/content_IOHVI2K4AYK6GOMOAVG93YBF6.html

为了简洁起见，我将讨论Stew Ashton的优化解决方案。

这是通过以下方式工作的:

-使用递归与遍历图
-对于每个新顶点，它:
-将其添加到顶点的嵌套表数组中
-构建具有从新顶点到子图中所有现有顶点的边的表
-对于这些边，检查没有不在现有边集中的边。即每个生成的边都在原始图中。

所以这是说，对于每个新的顶点:

这对子图中的所有现有顶点都有边吗？

如果否，则不会形成完全连接的子图。如果是的话，就是这样!

在SQL中，这看起来像:

create table relations (  
  p1 varchar2(1), p2 varchar2(1), 
  primary key ( p1, p2 ), 
  check ( p2 > p1 ) 
);

insert into relations   
  with rws ( p1 , p2 ) as (   
    select 'a' ,'b' from dual union all  
    select 'a' ,'c' from dual union all  
    select 'a' ,'d' from dual union all  
    
    select 'b' ,'c' from dual union all  
    select 'b' ,'d' from dual union all  
    
    select 'c' ,'d' from dual union all  
    select 'c' ,'e' from dual union all  
    select 'c' ,'f' from dual union all  
    
    select 'd' ,'e' from dual union all  
    
    select 'e' ,'f' from dual   
  )  
    select * from rws;

create or replace type ntt as table of varchar2(1);
/

with data(p, p1, p2, coll) as (   
  select a.p1, b.p1, b.p2, ntt(a.p1, a.p2, b.p2)   
  from   relations a    
  join   relations b   
  on     a.p2 = b.p1   
  and    (a.p1, b.p2) in (select * from relations)   
  union all   
  select a.p1, b.p1, b.p2, a.coll multiset union ntt(b.p2)   
  from   data a    
  join   relations b   
  on     a.p2 = b.p1   
  and (   
    select count(*)   
    from   table ( a.coll )   
    where  ( column_value, b.p2 ) not in (   
      select * from relations   
    )   
  ) = 0   
) cycle p, p1, p2 set is_cycle to '1' default '0'   
  select ps   
  from   data, lateral(   
    select '(' || listagg ( column_value, ',' )   
             within group ( order by column_value ) || ')' ps   
    from   table(coll)   
 );
 
PS          
(a,b,c)      
(a,b,d)      
(a,c,d)      
(b,c,d)      
(c,d,e)      
(c,e,f)      
(a,b,c,d)  
复制

注意: 对于这个问题，子图的最坏情况是2 ^ 顶点数。因此，对于一个平凡的100顶点图，可能的子图的数量是一个带有thirty digits!

This could be exceptionally slow!

要解决此问题，您可能需要在write上计算子图。请参阅此方法的实时SQL脚本中的包和触发器。注意这将计算移至插入/删除时间。这带来了自己的问题...

或者，值得一问: 你really需要all完全连接的子图？

我猜没有。在这种情况下，您可能正在寻找强连接的组件 (或类似的组件)。这在大图上运行更可行 :)

您可以使用我们的图技术来做到这一点。汉斯·维曼 (Hans Viehmann) 在7月16日的SQL办公时间会议上介绍了这些内容，我们在其中讨论了此问题。

此录音将很快可用。当它是实时的，你可以访问它:

https://asktom.oracle.com/pls/apex/f?p=100:551:::NO:551:P551_CLASS_ID,P551_STUDENT_ID:6204&cs=11921B2B179A7F0F930F234DE1BF1DCFC