Untuk menjaga agar algoritme traversing tidak kembali ke edge yang sudah dikunjungi, seseorang memang dapat menyimpan edge yang dikunjungi di suatu tempat. Seperti yang sudah Anda ketahui, Anda tidak akan mendapatkan banyak kesuksesan dengan rangkaian string. Namun, ada teknik "penggabungan nilai" lain yang dapat digunakan...
Anda harus memiliki satu kumpulan skalar tingkat skema yang berguna:
create or replace type arr_strings is table of varchar2(64);
Kemudian Anda dapat mengumpulkan edge yang dikunjungi ke koleksi tersebut di setiap iterasi:
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
;
Catatan
- Saya telah memroses sebelumnya grafik berarah menjadi grafik tidak berarah dengan
union-ing satu set tepi terbalik ke input. Itu seharusnya membuat predikat traversal rekursif lebih mudah dibaca. Semata-mata untuk tujuan saya membaca+menulis SQL dengan lebih mudah. Anda tidak perlu melakukan itu, tentu saja. - Saya ingat pernah mencoba sesuatu seperti ini beberapa tahun lalu di Oracle 11.2. Dan saya ingat bahwa itu gagal, meskipun saya tidak ingat mengapa. Pada 12.2, itu berjalan dengan baik. Coba saja 11g juga; Saya tidak punya yang tersedia.
- Karena setiap iterasi, selain traversal inner join, juga anti-join, saya sangat ragu bahwa ini akan menjadi lebih berkinerja. Namun, itu pasti memecahkan masalah penurunan jumlah sarang rekursif.
- Anda harus menyelesaikan sendiri urutan yang diinginkan, seperti yang mungkin Anda pahami dari komentar saya. :-)
Membatasi tepi yang ditinjau kembali menjadi nol
Di SQL, Anda tidak bisa. Solusi PostgreSQL yang Anda sebutkan melakukannya. Di Oracle, bagaimanapun, Anda tidak bisa. Anda harus, untuk setiap gabungan traversal, menguji baris untuk semua gabungan traversal lainnya. Dan itu berarti semacam agregasi atau analitik... yang dilarang Oracle dan mengeluarkan pengecualian ORA.
PLSQL untuk menyelamatkan?
Anda dapat melakukannya di PL/SQL. Berapa banyak kinerja yang seharusnya, tergantung pada berapa banyak memori yang ingin Anda habiskan untuk mengambil tepi dari DB vs. berapa banyak perjalanan bolak-balik SQL yang ingin Anda ambil untuk melintasi grafik dari node "saat ini" atau jika Anda bersedia menggunakan bahkan lebih banyak memori untuk menyimpan node yang dikunjungi dalam koleksi indexed-by-edge yang mewah vs. jika Anda lebih suka anti-gabung dengan arr_output biasa koleksi l_visited_nodes . Anda memiliki banyak pilihan, pilihlah dengan bijak.
Bagaimanapun, untuk skenario paling sederhana dengan penggunaan mesin SQL yang lebih berat, ini mungkin kode yang Anda cari...
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;
/
Saat dipanggil untuk simpul awal A dan menganggap grafik tidak berarah...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... itu menghasilkan...
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
Catatan
- Sekali lagi, saya tidak berusaha untuk memenuhi pesanan yang Anda minta, seperti yang Anda katakan tidak begitu penting.
- Ini melakukan beberapa (tepatnya 5 untuk input contoh Anda) SQL bolak-balik ke
edgemeja. Itu mungkin atau mungkin bukan kinerja yang lebih besar jika dibandingkan dengan solusi SQL murni dengan kunjungan tepi yang berlebihan. Uji lebih banyak solusi dengan benar, lihat mana yang paling cocok untuk Anda. - Bagian kode khusus ini akan bekerja pada 12c dan lebih tinggi. Untuk 11g dan lebih rendah, Anda harus mendeklarasikan
rec_outputdanarr_outputjenis pada tingkat skema.
