För att hålla den korsande algoritmen borta från att återvända till redan besökta kanter, kan man verkligen behålla de besökta kanterna någonstans. Som du redan har fått reda på kommer du inte att få mycket framgång med en strängsammansättning. Det finns dock andra användbara "värdesammansättningstekniker" tillgängliga...
Du måste ha en praktisk samling skalärer på schemanivå till ditt förfogande:
create or replace type arr_strings is table of varchar2(64);
Och sedan kan du samla de besökta kanterna till den samlingen i varje iteration:
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, from_id, to_id, edge_desc, visited_edges) as (
select 1, from_id, to_id, edge_desc,
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
;
Anteckningar
- Jag förbearbetade det riktade diagrammet till ett icke-riktat diagram av
union-ing av en uppsättning omvända kanter till ingången. Det borde göra de rekursiva traversalpredikaten lättare att läsa. Enbart för mina syften att lättare läsa+skriva av SQL. Du behöver naturligtvis inte göra det. - Jag minns att jag provade något liknande för några år sedan på Oracle 11.2. Och jag minns att det misslyckades, även om jag inte kommer ihåg varför. Den 12.2 gick det OK. Prova bara på 11g också; Jag har ingen tillgänglig.
- Eftersom varje iteration, förutom den genomgående inre sammanfogningen, också är en anti-join, tvivlar jag uppriktigt på att detta kommer att bli mer prestanda. Men det löser definitivt problemet med att minska antalet rekursiva häckningar.
- Du måste lösa den önskade beställningen på egen hand, som du förmodligen förstod av mina kommentarer. :-)
Begränsa de återbesökta kanterna till noll
I SQL kan du inte. PostgreSQL-lösningen du nämnde gör det. I Oracle kan du däremot inte. Du måste, för varje övergångskoppling, testa rader för alla andra övergångskopplingar. Och det skulle innebära någon form av aggregering eller analys... som Oracle förbjuder och kastar ut ett ORA-undantag.
PLSQL till undsättning?
Du kan dock göra det i PL/SQL. Hur mycket prestanda det ska vara beror på hur mycket minne du vill spendera på att förhämta kanter från DB kontra hur många SQL roundtrips du är villig att ta för att korsa grafen från "aktuella" noder eller om du är villig att använda ännu mer minne för att behålla de besökta noderna i en fancy indexerad-för-kant-samling jämfört med om du hellre anti-join mot en vanlig arr_output samling l_visited_nodes . Du har flera val, välj klokt.
Hur som helst, för det enklaste scenariot med tyngre användning av SQL-motor, kan det här vara koden du letar efter...
create or replace
package pkg_so_recursive_traversal
is
type rec_output is record (
from_id edge.from_id%type,
to_id edge.to_id%type,
lvl integer
);
type arr_output is table of rec_output;
function traverse_a_graph
( i_from in arr_strings
, i_is_directed in varchar2 default 'NO' )
return arr_output
pipelined;
end pkg_so_recursive_traversal;
/
create or replace
package body pkg_so_recursive_traversal
is
function traverse_a_graph
( i_from in arr_strings
, i_is_directed in varchar2 )
return arr_output
pipelined
is
l_next_edges arr_output;
l_current_edges arr_output;
l_visited_edges arr_output := arr_output();
l_out rec_output;
i pls_integer;
l_is_directed varchar2(32) := case when i_is_directed = 'YES' then 'YES' else 'NO' end;
begin
select E.from_id, E.to_id, 0
bulk collect into l_next_edges
from table(i_from) F
join edge E
on F.column_value in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end)
where E.from_id != E.to_id;
l_out.lvl := 0;
loop
dbms_output.put_line(l_next_edges.count());
exit when l_next_edges.count() <= 0;
l_out.lvl := l_out.lvl + 1;
-- spool the edges to output
i := l_next_edges.first();
while i is not null loop
l_out.from_id := l_next_edges(i).from_id;
l_out.to_id := l_next_edges(i).to_id;
pipe row(l_out);
i := l_next_edges.next(i);
end loop;
l_current_edges := l_next_edges;
l_visited_edges := l_visited_edges multiset union l_current_edges;
-- find next edges
select unique E.from_id, E.to_id, 0
bulk collect into l_next_edges
from table(l_current_edges) CE
join edge E
on CE.to_id in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end)
or l_is_directed = 'NO' and CE.from_id in (E.from_id, E.to_id)
where E.from_id != E.to_id
and not exists (
select 1
from table(l_visited_edges) VE
where VE.from_id = E.from_id
and VE.to_id = E.to_id
);
end loop;
return;
end;
end pkg_so_recursive_traversal;
/
När anropas för startnoden för A och betraktar grafen som oriktad...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... det ger...
FROM_ID TO_ID LVL
---------- ---------- ----------
A B 1
C A 1
C E 2
B D 2
C F 2
E B 2
G D 3
H F 3
G I 4
Anteckningar
- Återigen, jag ansträngde mig inte för att behålla den beställning du begärde, eftersom du sa att det inte är så viktigt.
- Detta gör flera (exakt 5 för dina exempelingångar) SQL-rundturer till
edgetabell. Det kan eller kanske inte är en större prestandaträff jämfört med den rena SQL-lösningen med redundanta kantbesök. Testa fler lösningar ordentligt, se vilken som fungerar bäst för dig. - Denna speciella kodbit fungerar på 12c och högre. För 11g och lägre måste du deklarera
rec_outputocharr_outputtyper på schemanivå.