Найдите все узлы в модели списка смежности с помощью oracle connect by

Учитывая следующую модель:

create table child_parent (
  child number(3),
  parent number(3)
);

Учитывая следующие данные:

insert into child_parent values(2,1);
insert into child_parent values(3,1);
insert into child_parent values(4,2);
insert into child_parent values(5,2);
insert into child_parent values(6,3);

получается следующее дерево:

        1
       / \
      2   3
     / \   \
    4   5   6

Теперь я могу найти родителей 5 следующим образом:

SELECT parent FROM child_parent START WITH  child = 5 
              CONNECT BY NOCYCLE PRIOR parent = child;

Но как мне получить все узлы (1,2,3,4,5,6), начиная с 5?


sql oracle tree adjacency-list
person haschibaschi    schedule 28.04.2013    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Синтаксис Oracle CONNECT BY предназначен для обхода иерархических данных: он является однонаправленным, поэтому не подходит для представления графа, требующего двунаправленности. Невозможно пройти 2 -> 1 -> 3 в одном запросе, что вам нужно сделать, чтобы получить все узлы, начиная с 5.

Давным-давно я ответил на вопрос о выравнивании узлов в иерархии (транзитивное замыкание AKA), т.е. если 1->2->3 верно, то `1->3' также верно. Он ссылается на статью, в которой демонстрируется решение PL/SQL для создания всех ребер и их сохранения в таблице. Аналогичное решение можно использовать и в этом случае. Но, очевидно, это практично только в том случае, если узлы в графе не меняются очень часто. Так что, возможно, это будет иметь ограниченное применение. В любом случае, узнайте больше.

person APC    schedule 28.04.2013

arrow_upward
2
arrow_downward

Наконец я придумал решение, похожее на это:

  SELECT child FROM child_parent START WITH parent =
   (
    SELECT DISTINCT parent FROM   
     (
      SELECT parent
      FROM child_parent
      WHERE CONNECT_BY_ISLEAF = 1
        START WITH child = 5
        CONNECT BY PRIOR parent = child
      UNION
      SELECT parent
      FROM child_parent
      WHERE parent = 5
     ) 
   )
   CONNECT BY NOCYCLE PRIOR child = parent
   UNION
   SELECT DISTINCT parent FROM   
   (
    SELECT parent
    FROM child_parent
    WHERE CONNECT_BY_ISLEAF = 1
      START WITH child = 5
      CONNECT BY PRIOR parent = child
    UNION
    SELECT parent
    FROM child_parent
    WHERE parent = 5
   );

Он работает со всеми узлами для предоставленного примера. Но если у одного из листьев есть второй родитель, а начальная точка находится над этим узлом или в другой ветке, это не сработает.

Но для меня это достаточно хорошо.

Решение для получения всех узлов в графе может быть следующим: реализовать запрос, противоположный приведенному выше (сверху вниз), а затем выполнить их (снизу вверх, сверху вниз) в обратном порядке, пока вы не найдете больше новых узлов. Для этого потребуется PL/SQL, и я также не знаю о производительности.

person haschibaschi    schedule 30.04.2013

arrow_upward
1
arrow_downward

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

Попробуйте запрос ниже, он будет проходить по всему дереву, но вам придется начинать с корня, а не с листа:

select * from (
SELECT child FROM child_parent START WITH  parent = 1 
              CONNECT BY NOCYCLE PRIOR child = parent
union
select 1 from dual)
order by child;

вы можете заменить «1» любым другим корневым элементом, все элементы ниже этого корня будут напечатаны, включая этот корень.

person Lokesh    schedule 28.04.2013