Направленный граф SQL

Question

У меня есть следующий набор данных, который представляет узлы в ориентированном графе.

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

Визуальное представление: http://esser.hopto.org/temp/image1.JPG

Используя этот набор данных, я хочу пользователю вводить уровень (например, 2), и это возвращает все узлы 2 «хмель» от конкретного узла):

NODE_FROM NODE_TO 

TG  GC 
TG  GG 
AT  TG 
GT   TG 

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

Моя текущая попытка выглядит следующим образом:

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

Как вы можете видеть, отношения: GT -> TG отсутствует.

Answer 1

Так ваш график выглядит следующим образом:

Вы можете использовать START WITH/CONNECT BY функцию Oracle, чтобы делать то, что вы хотите. Если мы начнем с узла GA, мы можем достигнуть всех узлов в графике, как показано ниже.

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; 

Выход:

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 

ПРИМЕЧАНИЕ Поскольку ваш граф имеет циклы, важно использовать синтаксис NOCYCLE на CONNECT BY, иначе это не будет работать.

EDITED ОТВЕТ НА ОСНОВЕ ПОСЛЕДНЕЙ Правки OP

Прежде всего, я полагаю, что «2 хмель» вы имеете в виду «в большинстве 2 хмель», потому что ваш текущий запрос использует level <= 2. Если вы хотите ровно 2 прыжка, это должно быть level = 2.

В обновленном графике (image2.JPG) нет пути от AT до GT, который принимает 2 перелета, поэтому запрос возвращает то, что я ожидаю. От AT до GT мы можем пойти AT->TG->GC->CG->GT, но это 4 прыжка, что больше 2, поэтому вы не получите этот результат.

Если вы ждете, чтобы быть в состоянии достигнуть AT к GT в 2 хмель, то вам нужно добавить ребро между ТГ и GT, как это:

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

Теперь, когда вы запускаете запрос, будете получить эти данные обратно:

NODE_FROM NODE_TO AT TG TG GC TG GG TG GT

Помните, что START WITH/CONNECT BY будет работать только если между узлами существует путь.На вашем графике (до того, как я добавил новый край выше), нет пути для AT->TG->GT, поэтому вы не возвращаете результат.

Теперь, если вы добавили кромку TG->AT, тогда у нас был бы путь GT->TG->AT. Итак, в этом случае AT находится в 2 прыжках от GT (т. Е. Мы идем в обратном направлении, начиная с GT и заканчивая AT). Но чтобы найти эти пути, вам нужно установить START WITH node_from = 'GT'.

Если ваша цель - найти все пути от стартового узла до любого целевого узла, который находится на уровне < = 2 перелета или менее, то вышеприведенное должно работать.

Однако, если вы хотите, чтобы все находили все пути с какого-либо целевого узла обратно на исходный узел (т. Е. Обратный пример, который я дал, от GT->TG->AT), то это не будет работать здесь. Вам нужно будет запустить запрос для всех узлов в графике.

Подумайте, START WITH/CONNECT BY как делать depth first search. Он будет идти везде, где это возможно, из стартового узла. Но это не будет делать больше.

Резюме:

Я думаю, что запрос работает нормально, учитывая вышеуказанные ограничения. Я объяснил, почему путь GT-TG не возвращается, поэтому я надеюсь, что это имеет смысл.

Имейте в виду, что если вы также пытаетесь пройти обратные пути, вам придется перебирать каждый узел и запускать запрос, каждый раз меняя узел START WITH.

Answer 2

Похоже, что вам нужно получить копию Joe Celko's Trees and Hierarchies in SQL for Smarties.