Oracle иерархический запрос по неиерархическим данным

Question

У меня есть данные в таблице Oracle, которая организована в виде графика, который может содержать циклы (см. Пример).

     CREATE TABLE T (parent INTEGER, child INTEGER)
               AS select 1 parent, 2 child from dual
        union all select 1 parent, 8 child from dual
        union all select 2 parent, 3 child from dual
        union all select 2 parent, 4 child from dual
        union all select 2 parent, 8 child from dual
        union all select 3 parent, 4 child from dual
        union all select 3 parent, 6 child from dual
        union all select 4 parent, 5 child from dual
        union all select 5 parent, 8 child from dual
        union all select 6 parent, 5 child from dual
        union all select 7 parent, 3 child from dual
        union all select 7 parent, 5 child from dual
        union all select 8 parent, 6 child from dual

Моя цель - получить всех узлов, которые являются потомками (дети, дети детей и т. Д.) Узла X. Скажем, 2 . Мой ожидаемый результат тогда: 3, 4, 5, 6, 8.

Я знаю, что могу разработать запрос следующим образом:

SELECT child, sys_connect_by_path(child,'/')
   FROM T
  START WITH parent = 2
CONNECT BY NOCYCLE PRIOR child = PARENT;

Проблема с таким запросом состоит в том, что он будет проходить через все возможные пути, пока они не пройдут цикл, и их слишком много в моих реальных данных. Результат состоит из множества дубликатов - вот оно:

child | sys_connect_by_path (for information)
3     | /3
4     | /3/4
5     | /3/4/5
8     | /3/4/5/8
6     | /3/4/5/8/6
6     | /3/6
5     | /3/6/5
8     | /3/6/5/8
4     | /4
5     | /4/5
8     | /4/5/8
6     | /4/5/8/6
8     | /8
6     | /8/6
5     | /8/6/5

Мои фактические данные намного сложнее. стоимость выполнения такого запроса настолько велика, что мое табличное пространство TEMP, которое было автоматически расширяемым, достигло 10 ГБ (первоначально 500 МБ), а моя база данных фактически сломалась из-за переполнения диска.

Я пытался сконструировать запрос следующим образом (рекурсивное предложение WITH):

WITH descendants(node) AS
( SELECT 2 node FROM dual
  UNION ALL
  (
  SELECT child
    FROM T
   INNER JOIN descendants D
      ON T.parent = D.node
   MINUS SELECT node FROM descendants
  )
)
SELECT * FROM descendants

Проблема, с которой я сталкиваюсь:

• в Oracle 10g это не реализовано (ORA-32033: unsupported column aliasing, а некоторые клиенты используют Oracle 9 или 10),
• с Oracle 11g, я получаю ORA-32041: UNION ALL operation in recursive WITH clause must have only two branches. Если я уберу предложение МИНУС, я получу циклы (ORA-32044: cycle detected while executing recursive WITH query).

Как бы вы запросили мои исходные данные, чтобы эффективно получить эти узлы 3, 4, 5, 6, 8? PL / SQL решения также приветствуются.

Спасибо.

Answer 1

Какова ожидаемая максимальная глубина для достижения любого дочернего узла?

Если он относительно небольшой, вы можете зацикливаться, проверяя уже посещенные вами узлы, примерно так ...

(Обратите внимание, я не эксперт Oracle, так что это ближе к псевдокоду с небольшим количеством реального SQL-кода)

CREATE TABLE myMap (parent INT, child INT);

INSERT INTO myTable SELECT NULL, 2 FROM DUAL;

WHILE (SQL%ROWCOUNT > 0)
LOOP

  INSERT INTO
    myMap
  SELECT DISTINCT
    dataMap.parent,
    dataMap.child
  FROM
    myMap
  INNER JOIN
    dataMap
      ON myMap.child = dataMap.parent
  WHERE
    NOT EXISTS (SELECT * FROM myMap WHERE parent = dataMap.parent)

END LOOP;

В зависимости от производительности, вы также можете захотеть depth поле в myMap;оптимизировать объединение так, чтобы объединяться только на самых последних узлах.Это будет означать два индекса;один для JOIN (depth) и один для NOT EXISTS (parent).

EDIT

Добавлено ключевое слово DISTINCT, чтобы избежать следующего случая ...
- Узел 2 сопоставляется с 3 и 4
- Узлы 3 и 4 сопоставляются с узлом 5
- Все дочерние узлы узла 5 теперь будут обрабатываться дважды

GROUP BY или многими другимиварианты, могут быть использованы для удовлетворения этого вместо DISTINCT.Просто одного «НЕ СУЩЕСТВУЕТ» не достаточно.

Answer 2

Это может помочь, пока количество посещений не превысит 4000 байт.Циклы не должны быть возможны, но линия приведена в качестве примера.

   WITH descendants(node, lvl, pth, visited) AS
    (
    SELECT child node, 1, cast(child as varchar2(4000)), '/'||listagg(child,'/') within group (order by child) over()||'/'
      FROM t 
     where parent = 2
     UNION ALL
    SELECT child, lvl+1, pth||'/'||child, D.visited||listagg(child,'/') within group (order by child) over()||'/'
      FROM T
     INNER JOIN descendants D
        ON T.parent = D.node
     WHERE D.visited not like '%/'||child||'/%'
    )
    cycle node set cyc to '1' default '0' 
    SELECT distinct node
      FROM descendants
     order by node
    ;

Answer 3

Я сам с этим не работал, но как насчет CONNECT BY с опцией NOCYCLE? Это должно прекратить обход дерева, когда оно видит петлю. Oracle 11i определенно имеет это, я думаю, что это произошло где-то в период Oracle 10g.