Направленный граф 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

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

Вы можете использовать функцию Oracle START WITH/CONNECT BY, чтобы делать то, что вы хотите.Если мы начнем с узла 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, иначе это не сработает.

РЕДАКТИРОВАНИЕ ОТВЕТА НА ОСНОВЕ ПОСЛЕДНИХ РЕДАКТОВ ОТ OP

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

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

Если вы ожидаете, что сможете достичьПерейдите к GT за 2 прыжка, затем вам нужно добавить грань между TG и 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 прыжков или меньшепрочь, тогда вышеупомянутое должно работать. </p>

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

Думайте о START WITH/CONNECT BY как о выполнении поиска в глубину .Он будет идти везде, где только может, начиная с узла.Но он не собирается делать больше, чем это.

Резюме:

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

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

Answer 2

Похоже, вам нужно получить копию Деревья и иерархии Джо Селко в SQL для умников .