graf skierowany w Oracle SQL przy użyciu kwerendy rekurencyjnej odwiedzenie każdego węzła tylko raz

Question

Opis

W naszej domenie problemu pracujemy nad zestawem krawędzi, które łączyć ze sobą tworząc wykres. Począwszy od danego węzła (lub węzłów), musimy wyświetlić wszystkie łącza na całym wykresie, które są podłączone do danego węzła (lub węzłów). Musimy pokazać te linki od lewej do prawej, od góry do dołu.

Mamy działającą kwerendę dla tego problemu dla wykresów z ograniczoną liczbą pętli. Większa liczba pętli wydłuża czas wykonania wykładniczo.

Musimy ograniczyć odwiedziny do tego samego węzła podczas rekursji, aby uzyskać działające rozwiązanie.

Poniższy przykład zawiera tylko jedną pętlę, ale ta pojedyncza pętla powoduje już 86 dodatkowych i nieaktualnych wierszy.

W podobnych postach dostarczane są rozwiązania dla PostgreSQL przy użyciu ROW i DOWOLNYCH operatorów, ale nie mogłem znaleźć rozwiązania Oracle.

Poszukujemy alternatywy dla naszego rozwiązania lub sposobu ograniczenia liczby odwiedzin na tych samych krawędziach.

Każda pomoc jest bardzo doceniana!

podobne

Visiting a directed graph as if it were an undirected one, using a recursive query zapewnia rozwiązanie PostgreSQL. Musimy używać Oracle11g.

Przykład

Krawędzie

A-B, B-D, C-A, C-E, C-F, H-F, E-B, G-D, G-I 

graficzny

A 
/ \ 
C - E - B - D 
    \  /
H - F G - I 

DLL i DML

CREATE TABLE EDGE (
    FROM_ID VARCHAR(10), 
    TO_ID VARCHAR(10) 
); 

INSERT INTO EDGE VALUES ('A', 'B'); 
INSERT INTO EDGE VALUES ('E', 'B'); 
INSERT INTO EDGE VALUES ('C', 'E'); 
INSERT INTO EDGE VALUES ('C', 'A'); 
INSERT INTO EDGE VALUES ('C', 'F'); 
INSERT INTO EDGE VALUES ('B', 'D'); 
INSERT INTO EDGE VALUES ('G', 'D'); 
INSERT INTO EDGE VALUES ('H', 'F'); 
INSERT INTO EDGE VALUES ('G', 'I'); 

Wejście

nodes: 'A' 

wymaganej wydajności

C A 
C E 
C F 
H F 
A B 
E B 
B D 
G D 
G I 

obecne rozwiązanie

Nasze obecne rozwiązanie zwraca dokładnie to, czego potrzebujemy, ale jak wspomniałem bove każda dodatkowa pętla wydłuża czas wykonania wykładniczo.

SELECT 
    c.LVL, 
    c.FROM_ID, 
    c.TO_ID, 
    CASE 
    WHEN lag(C.TO_ID) 
     OVER (
     PARTITION BY C.LVL 
     ORDER BY C.LVL, C.TO_ID) = C.TO_ID 
    THEN C.LVL || '-' || C.TO_ID 
    WHEN lead(C.TO_ID) 
     OVER (
     PARTITION BY C.LVL 
     ORDER BY C.LVL, C.TO_ID) = C.TO_ID 
    THEN C.LVL || '-' || C.TO_ID 
    ELSE C.LVL || '-' || C.FROM_ID 
    END GROUP_ID 
FROM (
     WITH chain(LVL, FROM_ID, TO_ID) AS (
     SELECT 
      1   LVL, 
      root.FROM_ID FROM_ID, 
      root.TO_ID TO_ID 
     FROM EDGE root 
     WHERE root.TO_ID IN (:nodes) 
       OR (root.FROM_ID IN (:nodes) AND NOT EXISTS(
      SELECT * 
      FROM EDGE 
      WHERE TO_ID IN (:nodes) 
     )) 
     UNION ALL 
     SELECT 
      LVL + 
      CASE 
      WHEN previous.TO_ID = the_next.FROM_ID 
      THEN 1 
      WHEN previous.TO_ID = the_next.TO_ID 
      THEN 0 
      WHEN previous.FROM_ID = the_next.FROM_ID 
      THEN 0 
      ELSE -1 
      END    LVL, 
      the_next.FROM_ID FROM_ID, 
      the_next.TO_ID TO_ID 
     FROM EDGE the_next 
      JOIN chain previous ON previous.TO_ID = the_next.FROM_ID 
            OR the_next.TO_ID = previous.FROM_ID 
            OR (previous.TO_ID = the_next.TO_ID AND previous.FROM_ID <> the_next.FROM_ID) 
            OR (previous.TO_ID <> the_next.TO_ID AND previous.FROM_ID = the_next.FROM_ID) 
     ) 
     SEARCH BREADTH FIRST BY FROM_ID SET ORDER_ID 
     CYCLE FROM_ID, TO_ID SET CYCLE TO 1 DEFAULT 0 
     SELECT 
     C.*, 
     row_number() 
     OVER (
      PARTITION BY LVL, FROM_ID, TO_ID 
      ORDER BY ORDER_ID) rank 
     FROM chain C 
     ORDER BY LVL, FROM_ID, TO_ID 
    ) C 
WHERE C.rank = 1; 

Answer 1

Dla utrzymania algorytmu przejazdu z powrotu do już odwiedzanych krawędzi, rzeczywiście można trzymać odwiedzone krawędzie gdzieś.Jak już się dowiedzieliście, nie osiągniecie większego sukcesu z łączeniem ciągów. Jednak istnieją inne użyteczne „wartość konkatenacji” techniki dostępne ...

Trzeba mieć jeden poręczny kolekcji schematu szczebla skalarów do Państwa dyspozycji:

create or replace type arr_strings is table of varchar2(64); 

A potem można zbierać odwiedzanych krawędzie do tej kolekcji w każdej iteracji:

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 
; 

Uwagi

1. Przetworzyłem wstępnie skierowany wykres na inny, niż union, tworząc zestaw odwróconych krawędzi do wejścia. To powinno ułatwić odczytanie predykatów rekurencyjnych. Wyłącznie dla moich celów łatwiejsze czytanie + pisanie kodu SQL. Oczywiście nie musicie tego robić.
2. Pamiętam, że próbowałem czegoś takiego kilka lat temu w Oracle 11.2. I pamiętam, że zawodziło, choć nie pamiętam dlaczego. W 12.2 przebiegło OK. Wypróbuj także 11g; Nie mam dostępnego.
3. Ponieważ każda iteracja, oprócz łączenia wewnętrznego, również antyłącza, szczerze wątpię, że to będzie bardziej wydajne. Jednak na pewno rozwiązuje problem obniżania liczby rekurencyjnych zagnieżdżeń.
4. Musisz samodzielnie rozwiązać żądane zamówienie, co prawdopodobnie wynika z moich komentarzy. :-)

Ograniczenie revisited krawędzie zero

W SQL, nie można. Wspomniane rozwiązanie PostgreSQL to robi. W Oracle jednak nie możesz. W przypadku każdego dołączenia podczas przechodzenia musisz wykonać test wierszy dla wszystkich pozostałych połączeń. A to oznaczałoby jakąś agregację lub analizę ... której Oracle zabrania i wyrzuca wyjątek ORA.

PLSQL na ratunek?

Można to jednak zrobić w języku PL/SQL. Jaka powinna być wydajność, zależy od tego, ile pamięci chcesz wydać na prefetching edge od DB vs. ile obietnic SQL, które chcesz wykonać, aby przemieścić wykres z "bieżących" węzłów lub jeśli chcesz użyć jeszcze więcej pamięci, aby utrzymywać odwiedzane węzły w fantazyjnej kolekcji zindywidualizowanej w stosunku do kontra, jeśli wolisz przeciwdziałać przeciwko regularnej kolekcji arr_outputl_visited_nodes. Masz wiele możliwości wyboru, wybierz mądrze.

W każdym razie, na najprostszym scenariuszu cięższymi wykorzystaniem silnika SQL, może to być kod szukasz ...

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; 

/

Wywołany do węzła wyjściowego o A i zważywszy na wykresie być nieukierunkowany ...

select * 
from table(pkg_so_recursive_traversal.traverse_a_graph(
     i_from => arr_strings('A'), 
     i_is_directed => 'NO' 
    )); 

... daje ...

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 

Uwagi

1. Znowu nie wkładać żadnego wysiłku, aby utrzymać kolejność Żądana, jak pan powiedział, to nie jest takie ważne.
2. Wykonuje wiele (dokładnie 5 dla przykładowych danych wejściowych) odwołań SQL do tabeli edge. To może, ale nie musi, być większym hitem wydajności w porównaniu z rozwiązaniem czysto SQL z nadmiarem odwiedzania krawędzi. Przetestuj więcej rozwiązań, sprawdź, który z nich działa najlepiej.
3. Ten konkretny fragment kodu działa na poziomie 12c i wyższym. Dla wersji 11g i niższej musisz zadeklarować typy rec_output i arr_output na poziomie schematu.