Aby se algoritmus procházení nevracel k již navštíveným hranám, skutečně lze navštívené hrany někde ponechat. Jak jste již zjistili, se zřetězením strun nedosáhnete velkého úspěchu. Existují však i další použitelné techniky „řetězení hodnot“...
Musíte mít k dispozici jednu praktickou kolekci skalárů na úrovni schématu:
create or replace type arr_strings is table of varchar2(64);
A pak můžete shromáždit navštívené hrany do této kolekce v každé iteraci:
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
;
Poznámky
- Předběžně jsem zpracoval orientovaný graf na neorientovaný pomocí
union-vložení sady zpětných hran na vstup. To by mělo usnadnit čtení predikátů rekurzivního procházení. Pouze pro mé účely snadnějšího čtení + zápisu SQL. Nemusíte to samozřejmě dělat. - Pamatuji si, že jsem něco takového před několika lety zkusil na Oracle 11.2. A pamatuji si, že to selhalo, i když si nepamatuji proč. 12.2 to běželo OK. Zkuste to také na 11g; Žádné nemám k dispozici.
- Vzhledem k tomu, že každá iterace dělá kromě vnitřního spojení traversal také anti-join, upřímně pochybuji, že to bude výkonnější. Určitě však řeší problém snížení počtu rekurzivních hnízdění.
- Jak jste pravděpodobně pochopili z mých komentářů, budete si muset požadovanou objednávku vyřešit sami. :-)
Omezení znovu navštívených hran na nulu
V SQL nemůžete. Řešení PostgreSQL, které jste zmínil, to dělá. V Oracle však nemůžete. Pro každé spojení procházení byste museli testovat řádky pro všechna ostatní spojení procházení. A to by znamenalo nějaký druh agregace nebo analýzy... což Oracle zakazuje a vyhazuje výjimku ORA.
Na záchranu PLSQL?
Můžete to však udělat v PL/SQL. Jak velký výkon by měl být, závisí na tom, kolik paměti chcete utratit za předběžné načítání hran z DB vs. kolik zpátečních cest SQL jste ochotni podniknout k procházení grafu z „aktuálních“ uzlů nebo zda jste ochotni použít ještě více paměti, abyste udrželi navštívené uzly v luxusní kolekci indexované podle okrajů, ve srovnání s tím, že se spíše bráníte připojování proti běžnému arr_output kolekce l_visited_nodes . Máte více možností, vybírejte moudře.
Každopádně pro nejjednodušší scénář s intenzivnějším používáním SQL motoru to může být kód, který hledáte...
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;
/
Při volání pro počáteční uzel A a vzhledem k tomu, že graf je neorientovaný...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... to dává...
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
Poznámky
- Opět jsem se nijak nesnažil zachovat objednávku, kterou jste požadovali, protože jste řekl, že to není tak důležité.
- Toto dělá několik (přesně 5 pro vaše příklady vstupů) zpětných SQL cest na
edgestůl. To může, ale nemusí být větší výkon ve srovnání s řešením čistě SQL s redundantní hraniční návštěvou. Pořádně otestujte více řešení a zjistěte, které vám vyhovuje nejlépe. - Tato konkrétní část kódu bude fungovat na verzi 12c a vyšší. Pro 11g a nižší budete muset deklarovat
rec_outputaarr_outputtypy na úrovni schématu.