Styret graf i Oracle SQL ved hjælp af rekursiv forespørgsel, der kun besøger hver node én gang

For at holde den krydsende algoritme ude af at vende tilbage til allerede besøgte kanter, kan man faktisk holde de besøgte kanter et sted. Som du allerede har fundet ud af, vil du ikke få den store succes med en strengsammenkædning. Der er dog andre brugbare "værdisammenkædning"-teknikker tilgængelige...

Du skal have en praktisk samling af skalarer på skemaniveau til din rådighed:

opret eller erstat typen arr_strings er tabel af varchar2(64); 

Og så kan du samle de besøgte kanter til den samling i hver iteration:

med nondirected$ som (vælg fra_id, to_id, fra_id||'-'||to_id som edge_desc fra kant, hvor from_id !=to_id union alle vælg to_id, from_id, from_id||'-'|||to_id som 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 ( vælg 1, from_id, to_id, edge_desc, arr_strings(edge_desc) fra nondirected$ R hvor from_id i (&nodes) -- union all -- vælg lvl+1, Y.from_id, Y.to_id, Y.edge_desc, X.visited_edges multiset union arr_strings(Y.edge_desc) fra graph$ X join nondirected $ Y på Y.from_id =X.to_id hvor ikke eksisterer (vælg 1 fra tabel(X.visited_edges) Z hvor Y.edge_desc =Z.column_value ))søgebredde først ved edge_desc sæt ordre_id cyklus edge_desc sæt is_cycle til 1 standard 0, ranked_graph$ as ( vælg C.*, row_number() over (partition efter edge_desc rækkefølge efter lvl, order_id) som rang$ fra graph$ C-- hvor is_cycle =0) vælg *fra ranked_graph$--hvor rang$ <=1order efter lvl, order_id; 

Noter

1. Jeg forbehandlede den rettede graf til en ikke-dirigeret af union -ing af et sæt omvendte kanter til input. Det skulle gøre de rekursive traversale prædikater nemmere at læse. Udelukkende for mit formål at nemmere læsning+skrivning af SQL. Det behøver du selvfølgelig ikke gøre.
2. Jeg kan huske, at jeg prøvede sådan noget for et par år siden på Oracle 11.2. Og jeg kan huske, at det mislykkedes, selvom jeg ikke kan huske hvorfor. Den 12.2 kørte det OK. Prøv det også med 11g; Jeg har ikke en tilgængelig.
3. Da hver iteration, ud over den traversale indre joinforbindelse, også er en anti-join, tvivler jeg oprigtigt på, at dette vil være mere performant. Men det løser helt sikkert problemet med at sænke antallet af rekursive rede.
4. Du bliver nødt til at løse den ønskede bestilling på egen hånd, som du sikkert har forstået ud fra mine kommentarer. :-)

Begrænsning af de genbesøgte kanter til nul

I SQL kan du ikke. Den PostgreSQL-løsning, du nævnte, gør det. I Oracle kan du dog ikke. Du skal, for hver gennemløbssammenføjning, teste rækker for alle andre krydsningssammenføjninger. Og det ville betyde en form for aggregering eller analyse... som Oracle forbyder og smider en ORA-undtagelse ud.

PLSQL til undsætning?

Du kan dog gøre det i PL/SQL. Hvor meget performant det formodes at være, afhænger af hvor meget hukommelse du vil bruge på at forhåndshente kanter fra DB vs. hvor mange SQL roundtrips du er villig til at tage for at krydse grafen fra "aktuelle" noder, eller om du er villig til at bruge endnu mere hukommelse til at holde de besøgte noder i en fancy indekseret-efter-kant-samling i forhold til hvis du hellere anti-join mod en almindelig arr_output samling l_visited_nodes . Du har flere valg, vælg med omhu.

I hvert fald, for det enkleste scenarie med tungere brug af SQL-motor, kan dette være den kode, du leder efter...

opret eller erstat pakke pkg_so_recursive_traversalistype rec_output er record (fra_id edge.from_id%type, to_id edge.to_id%type, lvl integer);type arr_output er tabel over rec_output;funktion traverse_a_graph (i_from i var_charis2-standardstrenge, jeg 'NEJ') return arr_output pipelined;end pkg_so_recursive_traversal;/create or replacepackage body pkg_so_recursive_traversalisfunction traverse_a_graph ( i_from in arr_strings , i_is_directed in varchar2 ) return arr_output pipelined_ges; l_current_edges arr_output; l_visited_edges arr_output :=arr_output(); l_out rec_output; i pls_integer; l_is_directed varchar2(32) :=tilfælde, når i_is_directed ='JA' så 'JA' ellers 'NEJ' slut; start vælg 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, når l_is_directed ='YES' så null else E.to_id end) hvor E.from_id !=E.to_id; l_out.lvl :=0; loop dbms_output.put_line(l_next_edges.count()); exit når l_next_edges.count() <=0; l_out.lvl :=l_out.lvl + 1; -- spool kanterne til output i :=l_next_edges.first(); mens i ikke er null loop l_out.from_id :=l_next_edges(i).from_id; l_out.to_id :=l_next_edges(i).to_id; rørrække(l_ud); i :=l_next_edges.next(i); endeløkke; l_current_edges :=l_next_edges; l_visited_edges :=l_visited_edges multiset union l_current_edges; -- find næste kanter vælg unik E.from_id, E.to_id, 0 bulk collect into l_next_edges from table(l_current_edges) CE join edge E på CE.to_id in (E.from_id, case when l_is_directed ='YES' then null else E) .to_id end) eller l_is_directed ='NO' og CE.from_id i (E.from_id, E.to_id) hvor E.from_id !=E.to_id og ikke eksisterer (vælg 1 fra tabel(l_visited_edges) VE hvor VE.from_id =E.from_id og VE.to_id =E.to_id ); endeløkke; return;end;end pkg_so_recursive_traversal;/ 

Når der kaldes til startknudepunktet A og betragter grafen som ikke-rettet...

vælg *fra tabel(pkg_so_recursive_traversal.traverse_a_graph( i_from => arr_strings('A'), i_is_directed => 'NEJ' )); 

... det giver...

FROM_ID TO_ID LVL---------------- ---------- ----------A B 1C A 1C E 2B D 2C F 2E B 2G D 3H F 3G I 4 

Noter

1. Igen, jeg gjorde ikke noget for at beholde den bestilling, du anmodede om, da du sagde, at det ikke er så vigtigt.
2. Dette udfører flere (nøjagtig 5 for dine eksempelinput) SQL-rundture til edge bord. Det er måske eller måske ikke et større præstationshit sammenlignet med den rene SQL-løsning med redundante kantbesøg. Test flere løsninger korrekt, og se, hvilken der fungerer bedst for dig.
3. Dette stykke kode fungerer på 12c og nyere. For 11g og derunder skal du angive rec_output og arr_output typer på skemaniveau.