SQL grafo orientato

Question

Ho il seguente insieme di dati che rappresenta nodi di un grafo orientato.

CREATE TABLE nodes (NODE_FROM VARCHAR2(10),
                    NODE_TO VARCHAR2(10));

INSERT INTO nodes VALUES('GT','TG');
INSERT INTO nodes VALUES('GG','GC');
INSERT INTO nodes VALUES('AT','TG');
INSERT INTO nodes VALUES('TG','GC');
INSERT INTO nodes VALUES('GC','CG');
INSERT INTO nodes VALUES('TG','GG');
INSERT INTO nodes VALUES('GC','CA');
INSERT INTO nodes VALUES('CG','GT');

Rappresentazione visiva: http://esser.hopto.org/temp/image1.JPG

Con questo insieme di dati, voglio un utente di immettere un livello (ad esempio 2) e questo restituisce tutti i nodi 2 "hop" di distanza da un nodo specifico):

NODE_FROM  NODE_TO

TG        GC
TG        GG
AT        TG
GT          TG

http://esser.hopto.org/temp/image2.JPG

Il mio attuale aspetto tentativo come questo:

SELECT node_from, node_to
  FROM nodes
  WHERE level <= 2   -- Display nodes two "hops" from 'AT'
START WITH node_from = 'AT'
CONNECT BY NOCYCLE PRIOR node_to = node_from
    OR    node_to = PRIOR node_from
GROUP BY node_from, node_to;

http://esser.hopto.org/temp/image3.JPG

Come si può vedere, la relazione:. GT -> TG manca

Answer 1

Quindi, il tuo aspetto grafico come questo:

È possibile utilizzare la funzione START WITH/CONNECT BY di Oracle a fare quello che vuoi. Se si parte al nodo GA, possiamo raggiungere tutti i nodi del grafo, come illustrato di seguito.

CREATE TABLE edges (PARENT VARCHAR(100), CHILD VARCHAR(100));

insert into edges values ('AT', 'TG');
insert into edges values ('CG', 'GT');
insert into edges values ('GA', 'AT');
insert into edges values ('GC', 'CA');
insert into edges values ('GC', 'CG');
insert into edges values ('GG', 'GC');
insert into edges values ('GT', 'TG');
insert into edges values ('TG', 'GA');
insert into edges values ('TG', 'GC');
insert into edges values ('TG', 'GG');
COMMIT;

SELECT *
  FROM edges
START WITH CHILD = 'GA'
CONNECT BY NOCYCLE PRIOR CHILD = PARENT;

Output:

    PARENT  CHILD
1   TG      GA
2   GA      AT
3   AT      TG
4   TG      GC
5   GC      CA
6   GC      CG
7   CG      GT
8   CG      GT
9   GC      CA

Nota Dal momento che il grafico ha cicli, è importante utilizzare la sintassi NOCYCLE sul CONNECT BY, altrimenti questo non funzionerà.

A CURA RISPOSTA Sulla base degli ultimi EDITS DA OP

Prima di tutto, suppongo che per "2 luppolo" si intende "al massimo 2 luppolo", perché la query corrente utilizza level <= 2. Se si desidera esattamente 2 luppolo, dovrebbe essere level = 2.

il grafico aggiornato (image2.jpg), non esiste un percorso da AT a GT che prende 2 luppolo, quindi la query sta tornando quello che mi aspetterei. Da AT per GT, possiamo andare AT->TG->GC->CG->GT, ma questo è di 4 luppolo, che è superiore a 2, quindi è per questo che non sono sempre quel risultato di nuovo.

Se vi aspettate di essere in grado di raggiungere AT a GT in 2 luppolo, allora è necessario aggiungere un bordo tra il TG e GT, in questo modo:

INSERT INTO nodes VALUES('TG','GT');

Ora, quando si esegue la query, si otterrà questo ritorno di dati:

NODE_FROM NODE_TO AT TG TG GC TG GG TG GT

Ricordate che START WITH/CONNECT BY sta andando a lavorare solo se v'è un percorso tra i nodi. Nel grafico (prima ho aggiunto il nuovo bordo di cui sopra), non v'è alcun percorso per AT->TG->GT, quindi è per questo che non stai ricevendo la schiena risultato.

Ora, se si aggiunge il TG->AT bordo, allora avremmo il GT->TG->AT percorso. Quindi, in questo caso AT è 2 luppolo lontano da GT (vale a dire che stiamo andando nella direzione inversa ora, a partire da GT e termina a AT). Ma per trovare quei sentieri, si avrebbe bisogno di impostare AVVIO CON node_from = 'GT'.

Se il vostro obiettivo è quello di trovare tutti i percorsi da un nodo di inizio di ogni nodo di destinazione che è di livello <= 2 luppolo o meno lontano, quindi quanto sopra dovrebbe funzionare.

Tuttavia, se si vuole a tutti trovare tutti i percorsi di alcuni bersaglio nodo di nuovo ad un nodo di origine (vale a dire l'esempio contrario ho dato, da GT->TG->AT), allora quella di non andare a lavorare qui. Avresti per eseguire la query per tutti i nodi del grafo.

Pensate START WITH/CONNECT BY come fare una profondità prima cercare . E 'intenzione di andare ovunque si può da un nodo di partenza. Ma non sta andando a fare di più di quello.

Riepilogo:

Credo che la query funziona bene, tenuto conto dei vincoli di cui sopra. Ho spiegato il motivo per cui il percorso GT-TG non viene restituito, quindi spero che abbia un senso.

Tenete a mente, tuttavia, se si sta cercando di percorrere percorsi inversi così, dovrete ciclo su ogni nodo e si esegue la query, cambiando il START WITH nodo di volta in volta.

Answer 2

Sembra che avete bisogno di ottenere una copia di Joe Celko Alberi e gerarchie in SQL per Smarties .