Para evitar que el algoritmo de recorrido regrese a los bordes ya visitados, uno puede mantener los bordes visitados en algún lugar. Como ya descubrió, no tendrá mucho éxito con una concatenación de cadenas. Sin embargo, existen otras técnicas utilizables de "concatenación de valores" disponibles...
Debe tener a su disposición una colección práctica de escalares a nivel de esquema:
create or replace type arr_strings is table of varchar2(64);
Y luego puede recopilar los bordes visitados de esa colección en cada iteración:
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
;
Notas
- Preprocesé el gráfico dirigido a uno no dirigido por
union-ing un conjunto de bordes inversos a la entrada. Eso debería hacer que los predicados transversales recursivos sean más fáciles de leer. Únicamente para mis propósitos de facilitar la lectura y escritura del SQL. No tienes que hacer eso, por supuesto. - Recuerdo haber intentado algo como esto hace algunos años en Oracle 11.2. Y recuerdo que estaba fallando, aunque no recuerdo por qué. En 12.2, funcionó bien. Pruébalo también con 11 g; No tengo ninguno disponible.
- Dado que cada iteración hace, además de la unión interna transversal, también una unión anti-unión, sinceramente dudo que esto vaya a ser más eficaz. Sin embargo, seguramente resuelve el problema de reducir el número de anidamientos recursivos.
- Tendrá que resolver el pedido deseado por su cuenta, como probablemente entendió por mis comentarios. :-)
Limitación de los bordes revisados a cero
En SQL, no puedes. La solución PostgreSQL que mencionaste sí lo hace. En Oracle, sin embargo, no puedes. Tendría que, para cada unión transversal, probar filas para todas las demás uniones transversales. Y eso significaría algún tipo de agregación o análisis... que Oracle prohíbe y lanza una excepción ORA.
¿PLSQL al rescate?
Sin embargo, puede hacerlo en PL/SQL. El rendimiento que se supone que debe tener depende de la cantidad de memoria que desea gastar en la obtención previa de los bordes de la base de datos frente a la cantidad de viajes de ida y vuelta de SQL que está dispuesto a realizar para atravesar el gráfico desde los nodos "actuales" o si está dispuesto a usar aún más memoria para mantener los nodos visitados en una elegante colección indexada por borde en lugar de si prefieres unirte contra un arr_output regular colección l_visited_nodes . Tienes múltiples opciones, elige sabiamente.
De todos modos, para el escenario más simple con un uso más intensivo del motor SQL, este podría ser el código que está buscando...
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;
/
Cuando se llama para el nodo inicial de A y considerando que el gráfico no está dirigido...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... produce...
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
Notas
- Nuevamente, no hice ningún esfuerzo por mantener el orden que solicitó, ya que dijo que no es tan importante.
- Esto está haciendo múltiples (exactamente 5 para sus entradas de ejemplo) viajes de ida y vuelta de SQL al
edgemesa. Eso puede o no ser un mayor impacto en el rendimiento en comparación con la solución de SQL puro con visitas perimetrales redundantes. Pruebe más soluciones correctamente, vea cuál funciona mejor para usted. - Esta pieza de código en particular funcionará en 12c y superior. Para 11g y menos tendrás que declarar el
rec_outputyarr_outputtipos en el nivel de esquema.
