Pour éviter que l'algorithme de traversée ne revienne sur des arêtes déjà visitées, on peut en effet conserver les arêtes visitées quelque part. Comme vous l'avez déjà découvert, vous n'obtiendrez pas beaucoup de succès avec une concaténation de chaînes. Cependant, il existe d'autres techniques utilisables de "concaténation de valeurs"...
Vous devez avoir à votre disposition une collection pratique de scalaires au niveau du schéma :
create or replace type arr_strings is table of varchar2(64);
Et ensuite, vous pouvez collecter les arêtes visitées dans cette collection à chaque itération :
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
;
Remarques
- J'ai prétraité le graphe dirigé en un graphe non dirigé par
union-ing un ensemble de fronts inverses à l'entrée. Cela devrait faciliter la lecture des prédicats de parcours récursifs. Uniquement dans le but de faciliter la lecture et l'écriture du SQL. Vous n'êtes pas obligé de le faire, bien sûr. - Je me souviens avoir essayé quelque chose comme ça il y a quelques années sur Oracle 11.2. Et je me souviens qu'il échouait, même si je ne me souviens pas pourquoi. Le 12.2, ça fonctionnait bien. Essayez-le également sur 11g; Je n'en ai pas de disponible.
- Étant donné que chaque itération fait, en plus de la jointure interne transversale, également une anti-jointure, je doute sincèrement que cela soit plus performant. Cependant, cela résout à coup sûr le problème de la réduction du nombre d'imbrications récursives.
- Vous devrez résoudre vous-même la commande souhaitée, comme vous l'avez probablement compris d'après mes commentaires. :-)
Limiter les arêtes revisitées à zéro
En SQL, vous ne pouvez pas. La solution PostgreSQL que vous avez mentionnée le fait. Dans Oracle, cependant, vous ne pouvez pas. Vous devrez, pour chaque jointure de traversée, tester les lignes pour toutes les autres jointures de traversée. Et cela signifierait une sorte d'agrégation ou d'analyse... qu'Oracle interdit et rejette une exception ORA.
PLSQL à la rescousse ?
Vous pouvez le faire en PL/SQL, cependant. Le degré de performance qu'il est censé être dépend de la quantité de mémoire que vous souhaitez consacrer à la prélecture des bords de la base de données par rapport au nombre d'allers-retours SQL que vous êtes prêt à effectuer pour parcourir le graphique à partir des nœuds "actuels" ou si vous êtes prêt à utiliser encore plus de mémoire pour conserver les nœuds visités dans une collection fantaisiste indexée par bord par rapport à si vous préférez l'anti-join avec un arr_output normal collection l_visited_nodes . Vous avez plusieurs choix, choisissez judicieusement.
Quoi qu'il en soit, pour le scénario le plus simple avec une utilisation plus intensive du moteur SQL, cela pourrait être le code que vous recherchez...
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;
/
Lorsqu'il est appelé pour le nœud de départ de A et en considérant le graphe comme non orienté...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... ça donne...
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
Remarques
- Encore une fois, je n'ai fait aucun effort pour conserver l'ordre que vous avez demandé, car vous avez dit que ce n'était pas si important.
- Cela fait plusieurs allers-retours SQL (exactement 5 pour vos exemples d'entrées) vers le
edgetable. Cela peut ou non être un impact plus important sur les performances par rapport à la solution purement SQL avec une visite de périphérie redondante. Testez plus de solutions correctement, voyez celle qui vous convient le mieux. - Ce morceau de code particulier fonctionnera sur 12c et supérieur. Pour 11g et moins, vous devrez déclarer le
rec_outputetarr_outputtypes au niveau du schéma.
