Graphique dirigé SQL

Question

J'ai le jeu de données suivant, qui représente des nœuds dans un graphe orienté.

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'); 

Représentation visuelle: http://esser.hopto.org/temp/image1.JPG

En utilisant cet ensemble de données, je veux un utilisateur d'entrer un niveau (par exemple 2) et cela retourne tous les nœuds 2 « houblon » loin d'un noeud spécifique):

NODE_FROM NODE_TO 

TG  GC 
TG  GG 
AT  TG 
GT   TG 

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

Ma tentative actuelle ressemble à ceci:

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

Comme vous pouvez le voir, la relation: GT -> TG est manquante.

Answer 1

Ainsi, votre graphique ressemble à ceci:

Vous pouvez utiliser la fonction d'Oracle START WITH/CONNECT BY pour faire ce que vous voulez. Si nous commençons au nœud GA, nous pouvons atteindre tous les nœuds du graphique, comme indiqué ci-dessous.

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; 

Sortie:

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 

NOTE Depuis votre graphique a des cycles, il est important d'utiliser la syntaxe NOCYCLE sur le CONNECT BY, sinon cela ne fonctionnera pas.

RÉPONSE ÉDITÉ SUR LA BASE EDITS PLUS TARD OP

Tout d'abord, je suppose que par « 2 bonds » vous voulez dire « dans la plupart des 2 sauts », parce que votre requête en cours utilise level <= 2. Si vous voulez exactement 2 sauts, cela devrait être level = 2.

Dans votre graphique mis à jour (image2.JPG), il n'y a pas de chemin de AT à GT qui prend 2 sauts, donc la requête retourne ce que je m'attendais. De AT à GT, nous pouvons aller AT->TG->GC->CG->GT, mais c'est 4 hops, ce qui est supérieur à 2, c'est pourquoi vous n'obtenez pas ce résultat.

Si vous prévoyez d'être en mesure d'atteindre AT GT dans 2 sauts, vous devez ajouter un bord entre TG et GT, comme ceci:

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

Maintenant lorsque vous exécutez votre requête, vous « ll récupérer ces données:

NODE_FROM NODE_TO AT TG TG GC TG GG TG GT

Rappelez-vous que START WITH/CONNECT BY va seulement le travail s'il y a un chemin entre les nœuds.Dans votre graphique (avant d'ajouter la nouvelle arête ci-dessus), il n'y a pas de chemin pour AT->TG->GT, c'est pourquoi vous ne récupérez pas le résultat. Maintenant, si vous avez ajouté le bord TG->AT, nous aurions le chemin GT->TG->AT. Donc, dans ce cas, AT est à deux bonds de GT (c'est-à-dire que nous allons dans le sens inverse, à partir de GT et se terminant à AT). Mais pour trouver ces chemins, vous devez définir START WITH node_from = 'GT'.

Si votre objectif est de trouver tous les chemins d'un nœud de départ à un nœud cible de niveau < = 2 sauts ou moins, alors ce qui précède devrait fonctionner. Toutefois, si vous souhaitez retrouver tous les chemins d'un nœud cible vers un nœud source (c'est-à-dire l'exemple inverse que j'ai donné, de GT->TG->AT), cela ne fonctionnera pas ici. Vous devez exécuter la requête pour tous les nœuds du graphique.

Pensez à START WITH/CONNECT BY en faisant depth first search. Ça va aller partout où il peut partir d'un nœud de départ. Mais ça ne va pas faire plus que ça.

Résumé:

Je pense que la requête fonctionne très bien, compte tenu des contraintes ci-dessus. J'ai expliqué pourquoi le chemin GT-TG n'est pas retourné, donc j'espère que cela a du sens. Toutefois, si vous essayez également de parcourir les chemins de retour, vous devrez effectuer une boucle sur chaque nœud et exécuter la requête, en changeant le nœud START WITH à chaque fois.

Answer 2

Semble que vous devez obtenir une copie de Joe Celko's Trees and Hierarchies in SQL for Smarties.