Um zu verhindern, dass der Traversierungsalgorithmus zu bereits besuchten Kanten zurückkehrt, kann man tatsächlich die besuchten Kanten irgendwo behalten. Wie Sie bereits herausgefunden haben, werden Sie mit einer Zeichenfolgenverkettung keinen großen Erfolg erzielen. Es sind jedoch andere verwendbare "Wertverkettungs"-Techniken verfügbar...
Sie müssen eine praktische Sammlung von Skalaren auf Schemaebene zur Verfügung haben:
create or replace type arr_strings is table of varchar2(64);
Und dann können Sie die besuchten Kanten in jeder Iteration zu dieser Sammlung sammeln:
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
;
Notizen
- Ich habe den gerichteten Graphen durch
unionzu einem nichtgerichteten vorverarbeitet -ing eine Reihe von umgekehrten Kanten an die Eingabe. Das sollte die rekursiven Traversierungsprädikate leichter lesbar machen. Ausschließlich für meine Zwecke des einfacheren Lesens + Schreibens des SQL. Das musst du natürlich nicht. - Ich erinnere mich, dass ich so etwas vor ein paar Jahren auf Oracle 11.2 ausprobiert habe. Und ich erinnere mich, dass es versagt hat, obwohl ich mich nicht erinnere, warum. Am 12.2 lief es OK. Probieren Sie es einfach auch mit 11g aus; Ich habe keine zur Verfügung.
- Da jede Iteration zusätzlich zum Traversal-Inner-Join auch einen Anti-Join macht, bezweifle ich ernsthaft, dass dies performanter sein wird. Es löst jedoch mit Sicherheit das Problem, die Anzahl der rekursiven Verschachtelungen zu verringern.
- Sie müssen die gewünschte Reihenfolge selbst auflösen, wie Sie wahrscheinlich aus meinen Kommentaren verstanden haben. :-)
Beschränkung der erneut besuchten Kanten auf null
In SQL können Sie das nicht. Die von Ihnen erwähnte PostgreSQL-Lösung tut dies. In Oracle ist dies jedoch nicht möglich. Sie müssten für jeden Traversal-Join Zeilen für alle anderen Traversal-Joins testen. Und das würde eine Art von Aggregation oder Analyse bedeuten ... was Oracle verbietet und eine ORA-Ausnahme auslöst.
PLSQL zur Rettung?
Sie können es jedoch in PL/SQL tun. Wie leistungsfähig es sein soll, hängt davon ab, wie viel Speicher Sie für das Vorabrufen von Kanten aus der DB aufwenden möchten und wie viele SQL-Roundtrips Sie bereit sind zu unternehmen, um den Graphen von "aktuellen" Knoten zu durchlaufen, oder ob Sie bereit sind, dies zu verwenden noch mehr Speicher, um die besuchten Knoten in einer ausgefallenen, nach Kanten indizierten Sammlung zu halten, im Vergleich zu einem Anti-Join gegen einen regulären arr_output Sammlung l_visited_nodes . Sie haben mehrere Möglichkeiten, wählen Sie mit Bedacht.
Wie auch immer, für das einfachste Szenario mit stärkerer Verwendung der SQL-Engine könnte dies der Code sein, nach dem Sie suchen ...
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;
/
Bei Aufruf für den Startknoten von A und den Graphen als ungerichtet betrachten...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... es ergibt ...
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
Notizen
- Auch hier habe ich mich nicht bemüht, die von Ihnen gewünschte Reihenfolge beizubehalten, da Sie sagten, dass dies nicht so wichtig ist.
- Dies führt mehrere (genau 5 für Ihre Beispieleingaben) SQL-Roundtrips zum
edgedurch Tisch. Dies kann im Vergleich zur reinen SQL-Lösung mit redundantem Edge-Besuch ein größerer Leistungseinbruch sein oder auch nicht. Testen Sie mehr Lösungen richtig und finden Sie heraus, welche für Sie am besten funktioniert. - Dieser spezielle Codeabschnitt funktioniert auf 12c und höher. Für 11g und niedriger müssen Sie
rec_outputdeklarieren undarr_outputTypen auf Schemaebene.
