在我们的问题域中,我们正在研究一组连接在一起形成图形的边.
从给定节点(或节点)开始,我们必须列出整个图中连接到给定节点(或节点)的所有链接.
我们必须从左到右,从上到下显示这些链接.
对于具有有限循环次数的图形,我们对此问题有一个有效的查询.较多的循环会以指数方式增加执行时间.
我们需要在递归期间限制对同一节点的访问以获得有效的解决方案.
下面的示例只包含一个循环,但是这个循环已经导致了86个额外的和过时的行.
在类似的帖子中,使用ROW和ANY运算符为postgresql提供了解决方案,但我找不到Oracle解决方案.
我们正在寻找替代解决方案或限制访问相同边缘的方式.
任何帮助是极大的赞赏！
类似
Visiting a directed graph as if it were an undirected one,using a recursive query在postgresql中提供了一个解决方案.
我们需要使用Oracle11g.
例
边缘
A-B,B-D,C-A,C-E,C-F,H-F,E-B,G-D,G-I
图形
A / \ C - E - B - D \ / H - F G - I
DDL和DML
CREATE TABLE EDGE (
FROM_ID VARCHAR(10),TO_ID VARCHAR(10)
);
INSERT INTO EDGE VALUES ('A','B');
INSERT INTO EDGE VALUES ('E','B');
INSERT INTO EDGE VALUES ('C','E');
INSERT INTO EDGE VALUES ('C','A');
INSERT INTO EDGE VALUES ('C','F');
INSERT INTO EDGE VALUES ('B','D');
INSERT INTO EDGE VALUES ('G','D');
INSERT INTO EDGE VALUES ('H','F');
INSERT INTO EDGE VALUES ('G','I');
输入
nodes: 'A'
要求的输出
C A C E C F H F A B E B B D G D G I
现行解决方案
我们当前的解决方案正是我们所需要的,但如上所述,每个额外的循环都会以指数方式增加执行时间.
SELECT
c.LVL,c.FROM_ID,c.TO_ID,CASE
WHEN lag(C.TO_ID)
OVER (
PARTITION BY C.LVL
ORDER BY C.LVL,C.TO_ID ) = C.TO_ID
THEN C.LVL || '-' || C.TO_ID
WHEN lead(C.TO_ID)
OVER (
PARTITION BY C.LVL
ORDER BY C.LVL,C.TO_ID ) = C.TO_ID
THEN C.LVL || '-' || C.TO_ID
ELSE C.LVL || '-' || C.FROM_ID
END GROUP_ID
FROM (
WITH chain(LVL,FROM_ID,TO_ID ) AS (
SELECT
1 LVL,root.FROM_ID FROM_ID,root.TO_ID TO_ID
FROM EDGE root
WHERE root.TO_ID IN (:nodes)
OR (root.FROM_ID IN (:nodes) AND NOT EXISTS(
SELECT *
FROM EDGE
WHERE TO_ID IN (:nodes)
))
UNION ALL
SELECT
LVL +
CASE
WHEN prevIoUs.TO_ID = the_next.FROM_ID
THEN 1
WHEN prevIoUs.TO_ID = the_next.TO_ID
THEN 0
WHEN prevIoUs.FROM_ID = the_next.FROM_ID
THEN 0
ELSE -1
END LVL,the_next.FROM_ID FROM_ID,the_next.TO_ID TO_ID
FROM EDGE the_next
JOIN chain prevIoUs ON prevIoUs.TO_ID = the_next.FROM_ID
OR the_next.TO_ID = prevIoUs.FROM_ID
OR (prevIoUs.TO_ID = the_next.TO_ID AND prevIoUs.FROM_ID <> the_next.FROM_ID)
OR (prevIoUs.TO_ID <> the_next.TO_ID AND prevIoUs.FROM_ID = the_next.FROM_ID)
)
SEARCH BREADTH FIRST BY FROM_ID SET ORDER_ID
CYCLE FROM_ID,TO_ID SET CYCLE TO 1 DEFAULT 0
SELECT
C.*,row_number()
OVER (
PARTITION BY LVL,TO_ID
ORDER BY ORDER_ID ) rank
FROM chain C
ORDER BY LVL,TO_ID
) C
WHERE C.rank = 1;
解决方法
您必须拥有一个方便的模式级标量集合：
create or replace type arr_strings is table of varchar2(64);
然后,您可以在每次迭代中收集到该集合的访问边：
with nondirected$as (
select from_id,to_id,from_id||'-'||to_id as edge_desc
from edge
where from_id != to_id
union all
select to_id,from_id,from_id||'-'||to_id as edge_desc
from edge
where (to_id,from_id) not in (
select from_id,to_id
from edge
)
),graph$(lvl,edge_desc,visited_edges) as (
select 1,arr_strings(edge_desc)
from nondirected$R
where from_id in (&nodes)
--
union all
--
select
lvl+1,Y.from_id,Y.to_id,Y.edge_desc,X.visited_edges multiset union arr_strings(Y.edge_desc)
from graph$X
join nondirected$Y
on Y.from_id = X.to_id
where not exists (
select 1
from table(X.visited_edges) Z
where Y.edge_desc = Z.column_value
)
)
search breadth first by edge_desc set order_id
cycle edge_desc set is_cycle to 1 default 0,ranked_graph$as (
select C.*,row_number() over (partition by edge_desc order by lvl,order_id) as rank$
from graph$C
-- where is_cycle = 0
)
select *
from ranked_graph$
--where rank$<= 1
order by lvl,order_id
;
笔记
>我通过将一组反向边结合到输入,将有向图预处理为非定向图.这应该使递归遍历谓词更容易阅读.仅仅为了我更容易阅读sql的写作目的.当然,你不必这样做.
>我记得几年前在Oracle 11.2上尝试这样的事情.我记得它失败了,虽然我不记得为什么.在12.2,它运行正常.也试试11g吧;我没有可用的.
>由于每次迭代都会执行,除了遍历内连接外,还有反连接,我真诚地怀疑这将是更高效的.但是,它肯定解决了降低递归嵌套数量的问题.
>您必须自己解决所需的顺序,正如您可能从我的评论中理解的那样.
