Aby uniemożliwić algorytmowi przemierzania powracanie do już odwiedzonych krawędzi, można rzeczywiście gdzieś zatrzymać odwiedzone krawędzie. Jak już się przekonałeś, konkatenacja ciągów nie odniesie większego sukcesu. Istnieją jednak inne użyteczne techniki „konkatenacji wartości”...
Musisz mieć do dyspozycji jedną poręczną kolekcję skalarów na poziomie schematu:
create or replace type arr_strings is table of varchar2(64);
Następnie możesz zebrać odwiedzone krawędzie do tej kolekcji w każdej iteracji:
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
;
Notatki
- Wstępnie przetworzyłem graf skierowany na nieskierowany przez
union-wprowadzenie zestawu odwróconych zboczy do wejścia. Powinno to sprawić, że predykaty przechodzenia rekurencyjnego będą łatwiejsze do odczytania. Wyłącznie dla moich celów łatwiejszego czytania + pisania SQL. Oczywiście nie musisz tego robić. - Pamiętam, że próbowałem czegoś takiego kilka lat temu na Oracle 11.2. I pamiętam, że zawodziło, choć nie pamiętam dlaczego. 12.2 działało OK. Po prostu spróbuj też 11g; Nie mam dostępnego.
- Ponieważ każda iteracja, oprócz wewnętrznego sprzężenia przechodzenia, działa również przeciw sprzężeniu, szczerze wątpię, czy będzie to bardziej wydajne. Jednak z pewnością rozwiązuje to problem zmniejszenia liczby zagnieżdżeń rekurencyjnych.
- Będziesz musiał samodzielnie rozwiązać żądaną kolejność, co prawdopodobnie zrozumiałeś z moich komentarzy. :-)
Ograniczenie ponownie odwiedzanych krawędzi do zera
W SQL nie możesz. Wspomniane rozwiązanie PostgreSQL to robi. W Oracle jednak nie możesz. W przypadku każdego sprzężenia przechodzenia należałoby przetestować wiersze dla wszystkich innych sprzężeń przechodzenia. A to oznaczałoby jakiś rodzaj agregacji lub analizy… której Oracle zabrania i odrzuca wyjątek ORA.
PLSQL na ratunek?
Możesz to jednak zrobić w PL/SQL. To, jaka ma być wydajność, zależy od tego, ile pamięci chcesz przeznaczyć na wstępne pobieranie krawędzi z bazy danych w porównaniu z liczbą okrążeń SQL, które chcesz wykonać, aby przemierzyć wykres z „bieżących” węzłów lub czy chcesz użyć jeszcze więcej pamięci, aby utrzymać odwiedzane węzły w fantazyjnej kolekcji indeksowanej według krawędzi w porównaniu z jeśli wolisz nieprzyłączać się do zwykłego arr_output kolekcja l_visited_nodes . Masz wiele możliwości, wybieraj mądrze.
W każdym razie, w najprostszym scenariuszu z intensywniejszym użyciem silnika SQL, może to być kod, którego szukasz...
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;
/
Po wywołaniu dla węzła początkowego A i biorąc pod uwagę, że wykres jest nieskierowany...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... daje...
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
Notatki
- Ponownie nie starałem się zachować zamówienia, o które prosiłeś, ponieważ powiedziałeś, że nie jest to takie ważne.
- Wykonuje to wiele (dokładnie 5 dla przykładowych danych wejściowych) SQL-owych okrążeń do
edgestół. To może, ale nie musi, być większym spadkiem wydajności w porównaniu z rozwiązaniem opartym na czystym SQL z nadmiarowym odwiedzaniem krawędzi. Przetestuj więcej rozwiązań prawidłowo, zobacz, które z nich działa dla Ciebie najlepiej. - Ten konkretny fragment kodu będzie działał na 12c i wyższych. Dla 11g i niższych będziesz musiał zadeklarować
rec_outputiarr_outputtypy na poziomie schematu.
