Om te voorkomen dat het passerende algoritme terugkeert naar reeds bezochte randen, kan men inderdaad de bezochte randen ergens houden. Zoals je al hebt ontdekt, zul je niet veel succes hebben met een string-aaneenschakeling. Er zijn echter andere bruikbare technieken voor het samenvoegen van waarden beschikbaar...
U moet over één handige verzameling scalairen op schemaniveau beschikken:
create or replace type arr_strings is table of varchar2(64);
En dan kunt u in elke iteratie de bezochte randen van die verzameling verzamelen:
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
;
Opmerkingen
- Ik heb de gerichte grafiek voorbewerkt tot een niet-gerichte grafiek door
union-ing een set van omgekeerde randen naar de ingang. Dat zou de recursieve traversale predikaten beter leesbaar moeten maken. Uitsluitend voor mijn doeleinden van gemakkelijker lezen + schrijven van de SQL. Dat hoef je natuurlijk niet te doen. - Ik herinner me dat ik een paar jaar geleden zoiets probeerde op Oracle 11.2. En ik herinner me dat het niet lukte, al weet ik niet meer waarom. Op 12.2 liep het goed. Probeer het ook eens op 11g; Ik heb er geen beschikbaar.
- Aangezien elke iteratie, naast de traversal inner join, ook een anti-join doet, betwijfel ik oprecht of dit beter zal presteren. Het lost echter zeker het probleem op van het verlagen van het aantal recursieve nestings.
- Je zult de gewenste bestelling zelf moeten oplossen, zoals je waarschijnlijk uit mijn opmerkingen hebt begrepen. :-)
De opnieuw bezochte randen beperken tot nul
In SQL kan dat niet. De PostgreSQL-oplossing die u noemde, doet het. In Oracle kan dat echter niet. U zou voor elke traversal join rijen moeten testen voor alle andere traversal joins. En dat zou een soort aggregatie of analyse betekenen... die Oracle verbiedt en een ORA-uitzondering weggooit.
PLSQL te hulp?
Je kunt het echter wel in PL/SQL doen. Hoeveel performant het zou moeten zijn, hangt af van hoeveel geheugen u wilt besteden aan het vooraf ophalen van randen van DB versus hoeveel SQL-roundtrips u bereid bent te nemen om de grafiek van "huidige" knooppunten te doorkruisen of als u bereid bent te gebruiken nog meer geheugen om de bezochte knooppunten in een mooie, per rand geïndexeerde verzameling te houden versus als je liever anti-join tegen een gewone arr_output verzameling l_visited_nodes . Je hebt meerdere keuzes, kies verstandig.
Hoe dan ook, voor het eenvoudigste scenario met zwaarder gebruik van SQL-engine, is dit misschien de code die u zoekt...
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;
/
Wanneer aangeroepen voor het startknooppunt van A en de grafiek als ongericht beschouwen...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... het levert...
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
Opmerkingen
- Nogmaals, ik heb geen enkele moeite gedaan om de door jou gevraagde bestelling te behouden, omdat je zei dat het niet zo belangrijk is.
- Dit is het doen van meerdere (precies 5 voor uw voorbeeldinvoer) SQL-roundtrips naar de
edgetafel. Dat kan al dan niet een grotere prestatiehit zijn in vergelijking met de pure-SQL-oplossing met redundante edge-bezoeken. Test meer oplossingen goed, kijk welke het beste voor u werkt. - Dit specifieke stukje code werkt op 12c en hoger. Voor 11g en lager moet je de
rec_output. aangeven enarr_outputtypen op schemaniveau.