oracle – 来自无向图的最小ID

使用Oracle 11g,我试图在ID对的无向图中找到最小的ID.

使用以下对：

create table unique_pairs ( ID1 INT,ID2 INT );
insert all 
    into unique_pairs (ID1,ID2) VALUES ( 1,2 )  
    into unique_pairs (ID1,3 )
    into unique_pairs (ID1,ID2) VALUES ( 4,2 )
    into unique_pairs (ID1,5 )
    into unique_pairs (ID1,ID2) VALUES ( 7,6 )
    into unique_pairs (ID1,ID2) VALUES ( 8,10 )
    into unique_pairs (ID1,ID2) VALUES ( 10,7 )
select * from dual;
commit;

我正在使用两个通过查询连接的联合来尝试在地图的两个方向上旅行：

select distinct a.ID1,a.ID2,min(a.ultimate_parent_id ) as ultimate_parent_id
from
(SELECT distinct ID1,ID2,connect_by_root(ID2) ultimate_parent_id
  FROM unique_pairs
CONNECT BY ID2 = prior ID1 AND ID2 != PRIOR ID2 
union
SELECT distinct ID1,connect_by_root(ID1) ultimate_parent_id
  FROM unique_pairs
CONNECT BY ID1 = prior ID2 AND ID1 != PRIOR ID1) a
group by a.ID1,a.ID2
order by 3;

我明白了：

ID1        ID2 ULTIMATE_PARENT_ID

1          2                  1
     1          3                  1
     4          2                  2
     4          5                  4
    10          7                  6
     7          6                  6
     8         10                  6

应该是这样的：

ID1        ID2 ULTIMATE_PARENT_ID

1          2                  1
     1          3                  1
     4          2                  1
     4          5                  1
    10          7                  6
     7          6                  6
     8         10                  6

我认为我的问题涉及这样一个事实：当我的数据是非方向性时,按功能连接意味着层次结构.任何帮助都会很棒,谢谢！

解决方法

Collapsar有一个非常冗长的描述,但这是一个非常简短的解决方案,符合您的要求.我离图形理论的日子太过分了,不像他那样解释它,但简单的解释是,由于你的unique_pairs代表无向图中的边,它可以在有向图中表示为ID1,ID2与ID2,ID1因此是我的第一个公用表表达式.使用该有向图,您可以像我的第二个公用表表达式一样计算所有连接的节点对.最后,您可以将原始unique_pairs表连接到ID1上的已连接对CTE,并将最小根节点作为ULTIMATE_PARENT_ID：

with dg1 as (
  select id1,id2 from unique_pairs
  union all
  select id2,id1 from unique_pairs
),cp as (
select id1,CONNECT_BY_ROOT id1 root
  from dg1
connect by nocycle prior id1 = id2 
)
select dg1.*,min(root) ULTIMATE_PARENT_ID
  from unique_pairs dg1
  join cp
    on cp.id1 = dg1.id1
  group by dg1.id1,dg1.id2
order by 1,2

见SQL Fiddle

| ID1 | ID2 | ULTIMATE_PARENT_ID |
|-----|-----|--------------------|
|   1 |   2 |                  1 |
|   1 |   3 |                  1 |
|   4 |   2 |                  1 |
|   4 |   5 |                  1 |
|   7 |   6 |                  6 |
|   8 |  10 |                  6 |
|  10 |   7 |                  6 |