Per evitare che l'algoritmo di attraversamento torni a bordi già visitati, si possono effettivamente mantenere i bordi visitati da qualche parte. Come hai già scoperto, non avrai molto successo con una concatenazione di stringhe. Tuttavia, sono disponibili altre tecniche utilizzabili di "concatenazione di valori"...
Devi avere a disposizione una pratica raccolta di scalari a livello di schema:
create or replace type arr_strings is table of varchar2(64);
E quindi puoi raccogliere i bordi visitati in quella raccolta in ogni iterazione:
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
;
Note
- Ho pre-elaborato il grafo orientato in uno non orientato mediante
union-ing un insieme di fronti inversi all'input. Ciò dovrebbe rendere più facili da leggere i predicati di attraversamento ricorsivi. Solo per i miei scopi di lettura + scrittura più facile dell'SQL. Non devi farlo, ovviamente. - Ricordo di aver provato qualcosa del genere alcuni anni fa su Oracle 11.2. E ricordo che stava fallendo, anche se non ricordo perché. Il 12.2 ha funzionato bene. Provalo anche con 11g; Non ne ho uno disponibile.
- Dato che ogni iterazione, oltre al traversal inner join, fa anche un anti-join, dubito sinceramente che questo sarà più performante. Tuttavia, risolve sicuramente il problema dell'abbassamento del numero di annidamenti ricorsivi.
- Dovrai risolvere da solo l'ordine desiderato, come probabilmente avrai capito dai miei commenti. :-)
Limitare a zero i bordi rivisitati
In SQL, non puoi. La soluzione PostgreSQL che hai menzionato lo fa. In Oracle, tuttavia, non puoi. Dovresti, per ogni traversal join, testare le righe per tutti gli altri traversal join. E ciò significherebbe una sorta di aggregazione o analisi... che Oracle vieta ed elimina un'eccezione ORA.
PLSQL in soccorso?
Puoi farlo in PL/SQL, però. Quanto dovrebbe essere performante, dipende da quanta memoria vuoi spendere per precaricare i bordi da DB rispetto a quanti roundtrip SQL sei disposto a fare per attraversare il grafico dai nodi "correnti" o se sei disposto a usare ancora più memoria per mantenere i nodi visitati in una fantasiosa raccolta indicizzata per bordo rispetto a se preferisci l'anti-unione contro un normale arr_output raccolta l_visited_nodes . Hai più scelte, scegli con saggezza.
Ad ogni modo, per lo scenario più semplice con un uso più intenso del motore SQL, questo potrebbe essere il codice che stai cercando...
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;
/
Quando viene chiamato per il nodo iniziale di A e considerando il grafico non orientato...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... cede...
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
Note
- Ancora una volta, non ho fatto alcuno sforzo per mantenere l'ordine che hai richiesto, poiché hai detto che non è così importante.
- Questo sta facendo più (esattamente 5 per gli input di esempio) SQL roundtrip fino al
edgetavolo. Questo potrebbe o meno essere un calo delle prestazioni maggiore rispetto alla soluzione SQL puro con visita ridondante del bordo. Testa più soluzioni correttamente, vedi quale funziona meglio per te. - Questo particolare pezzo di codice funzionerà su 12c e versioni successive. Per 11g e meno dovrai dichiarare il
rec_outputearr_outputtipi a livello di schema.
