Обнаружение цикла с рекурсивным подзапросом факторингом

Ответ 1

Из документации по CONNECT_BY_ISCYCLE:

CONNECT_BY_ISCYCLE возвращает 1 если в текущей строке есть дочерний элемент, который также является его предком

и что на CYCLE:

Считается, что строка образует цикл, если одна из ее строк-предков имеет одинаковые значения для столбцов цикла.

В вашем примере строка 2 имеет дочерний элемент, который также является его предком, но его id еще не был возвращен.

Другими словами, CONNECT_BY_ISCYCLE проверяет дочерние элементы (которые еще должны быть возвращены), в то время как CYCLE проверяет текущую строку (которая уже возвращена).

CONNECT BY основан на CTE, а рекурсивный CTE - на множествах.

Обратите внимание, что в документации Oracle по CYCLE упоминается "строка предка". Однако, вообще говоря, в рекурсивном CTE отсутствует понятие "строки предков". Это основанная на множестве операция, которая может дать результаты полностью вне дерева. Вообще говоря, якорная часть и рекурсивная часть могут даже использовать разные таблицы.

Поскольку для построения иерархических деревьев обычно используются рекурсивные CTE, Oracle решила добавить проверку цикла. Но из-за того, как рекурсивный CTE работает на основе множеств, обычно невозможно сказать, будет ли следующий шаг генерировать цикл или нет, потому что без четкого определения "цикла предков" условие цикла также не может быть определено.

Чтобы выполнить "следующий" шаг, весь "текущий" набор должен быть доступен, но для генерации каждой строки текущего набора (который включает в себя столбец цикла) нам просто нужны результаты "следующей" операции.

Это не проблема, если текущий набор всегда состоит из одной строки (как в CONNECT BY), но это проблема, если рекурсивная операция определена для набора в целом.

Еще не изучал Oracle 11, но SQL Server реализует рекурсивный CTE, просто скрывая за ними CONNECT BY, что требует наложения многочисленных ограничений (все из которых фактически запрещают все операции на основе множеств).

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

Как упоминалось ранее, MySQL вообще не реализует CTE (он также не реализует HASH JOIN или MERGE JOIN, только вложенные циклы, так что не удивляйтесь).

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

Обновить:

Рекурсивный CTE в SQL Server не более, чем замаскированный CONNECT BY. Смотрите эту статью в моем блоге для шокирующих деталей:

• SQL Server: действительно ли рекурсивные CTE основаны на множествах?

Ответ 2

PostgreSQL поддерживает иерархические запросы в стиле WITH, но не имеет автоматического обнаружения цикла. Это означает, что вам нужно написать свой собственный, а число возвращаемых строк зависит от того, как вы указываете условия соединения в рекурсивной части запроса.

Оба примера используют массив, если идентификаторы (называемые all_ids) для обнаружения циклов:

WITH recursive tr (id, parent_id, all_ids, cycle) AS (
    SELECT id, parent_id, ARRAY[id], false
    FROM t
    WHERE id = 1
    UNION ALL
    SELECT t.id, t.parent_id, all_ids || t.id, t.id = ANY(all_ids)
    FROM t
    JOIN tr ON t.parent_id = tr.id AND NOT cycle)
SELECT id, parent_id, cycle
FROM tr;

 id | parent_id | cycle
----+-----------+-------
  1 |         2 | f
  2 |         1 | f
  1 |         2 | t


WITH recursive tr (id, parent_id, all_ids, cycle) AS (
    SELECT id, parent_id, ARRAY[id], false
    FROM t
    WHERE id = 1
    UNION ALL
    SELECT t.id, t.parent_id, all_ids || t.id, (EXISTS(SELECT 1 FROM t AS x WHERE x.id = t.parent_id))
    FROM t
    JOIN tr ON t.parent_id = tr.id
    WHERE NOT t.id = ANY(all_ids))
SELECT id, parent_id, cycle
FROM tr;

 id | parent_id | cycle
----+-----------+-------
  1 |         2 | f
  2 |         1 | t

Ответ 3

AFAIK:

• MySQL не поддерживает рекурсивный CTE
• SQL Sever не поддерживает цикл обнаружение в рекурсивном CTE

Ответ 4

MySQL Server версии 5.0.45 не понравился with:

ОШИБКА 1064 (42000): у вас есть ошибка в синтаксисе SQL; проверить руководство, соответствующее вашей версии сервера MySQL для правильного синтаксис для использования рядом с tr (id, parent_id) as (select id, parent_id от t, где id = 1 объединение всех s 'в строке 1.

Ответ 5

WITH RECURSIVE s (master, slave, all_ids, cycle) AS
(
    SELECT master, slave, ARRAY[master], false FROM binding WHERE master=3477

    UNION ALL

    SELECT d.master, d.slave, all_ids || d.master, d.slave = ANY(all_ids)
    FROM
        binding AS d
    JOIN
        s
    ON (d.master = s.slave)
    WHERE NOT d.master = ANY(all_ids)
)
SELECT *
FROM s;

Я думаю, что лучше это условие d.slave = ANY(all_ids)

Ответ 6

Результаты подключения не всегда могут быть интуитивными.

Приведенные ниже запросы демонстрируют различные подходы к обнаружению циклов, начиная с id = 3 для графика на рисунке.

create table graph (id, id_parent) as
(select 2, 1 from dual
union all select 3, 1 from dual
union all select 4, 3 from dual
union all select 5, 4 from dual
union all select 3, 5 from dual)

SQL> select level lvl, graph.*, connect_by_iscycle cycle
  2    from graph
  3   start with id = 3
  4  connect by nocycle prior id = id_parent;

       LVL         ID  ID_PARENT      CYCLE
---------- ---------- ---------- ----------
         1          3          1          0
         2          4          3          0
         3          5          4          1
         1          3          5          0
         2          4          3          0
         3          5          4          1

6 rows selected.

SQL> select level lvl, graph.*, connect_by_iscycle cycle
  2    from graph
  3   start with id = 3
  4  connect by nocycle prior id = id_parent
  5         and prior id_parent is not null;

       LVL         ID  ID_PARENT      CYCLE
---------- ---------- ---------- ----------
         1          3          1          0
         2          4          3          0
         3          5          4          0
         4          3          5          1
         1          3          5          0
         2          4          3          0
         3          5          4          1

7 rows selected.

SQL> with t(id, id_parent) as
  2   (select *
  3      from graph
  4     where id = 3
  5    union all
  6    select g.id, g.id_parent
  7      from t
  8      join graph g
  9        on t.id = g.id_parent)
 10  search depth first by id set ord
 11  cycle id set cycle to 1 default 0
 12  select * from t;

        ID  ID_PARENT        ORD C
---------- ---------- ---------- -
         3          1          1 0
         4          3          2 0
         5          4          3 0
         3          5          4 1
         3          5          5 0
         4          3          6 0
         5          4          7 0
         3          5          8 1

8 rows selected.

Узел с id = 3 имеет двух родителей, поэтому в этом примере Oracle проходит два цикла.

(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)

а также

(5, 3) -> (3, 4) -> (4, 5)

Край (5, 3) отсутствует в результате первого запроса и первого цикла. В то же время край (5, 3) появляется в результате третьего запроса и второго цикла дважды.

Почему так? Вы можете проверить описание логики обнаружения цикла в ответе, предоставленном Quassnoi. На простом английском это означает, что

(1) connect by обнаруживает цикл, если дочерний идентификатор для текущей строки является частью идентификаторов, посещенных до сих пор

(2) rec с обнаруживает цикл, если идентификатор для текущей строки является частью идентификаторов, посещенных до сих пор

Результат второго запроса выглядит наиболее естественным, хотя есть дополнительный предикат, and prior id_parent is not null. В этом случае

(3) он обнаруживает цикл, если идентификатор для текущей строки является частью родительских идентификаторов, посещенных до сих пор

Все эти условия реализованы в столбцах cnt1, cnt2, cnt3 в следующем запросе.

SQL> with t(id, id_parent, path_id, path_id_parent, cnt1, cnt2, cnt3) as
  2   (select g.*,
  3           cast('->' || g.id as varchar2(4000)),
  4           cast('->' || g.id_parent as varchar2(4000)),
  5           0,
  6           0,
  7           0
  8      from graph g
  9     where id = 3
 10    union all
 11    select g.id,
 12           g.id_parent,
 13           t.path_id || '->' || g.id,
 14           t.path_id_parent || '->' || g.id_parent,
 15           regexp_count(t.path_id || '->', '->' ||
 16            (select id from graph c where c.id_parent = g.id) || '->'),
 17           regexp_count(t.path_id || '->', '->' || g.id || '->'),
 18           regexp_count(t.path_id_parent || '->', '->' || g.id || '->')
 19      from t
 20      join graph g
 21        on t.id = g.id_parent
 22    -- and t.cnt1 = 0
 23    -- and t.cnt2 = 0
 24    -- and t.cnt3 = 0
 25    )
 26  search depth first by id set ord
 27  cycle id set cycle to 1 default 0
 28  select * from t;

        ID  ID_PARENT PATH_ID         PATH_ID_PARENT  CNT1 CNT2 CNT3        ORD C
---------- ---------- --------------- --------------- ---- ---- ---- ---------- -
         3          1 ->3             ->1                0    0    0          1 0
         4          3 ->3->4          ->1->3             0    0    0          2 0
         5          4 ->3->4->5       ->1->3->4          1    0    0          3 0
         3          5 ->3->4->5->3    ->1->3->4->5       1    1    1          4 1
         3          5 ->3             ->5                0    0    0          5 0
         4          3 ->3->4          ->5->3             0    0    0          6 0
         5          4 ->3->4->5       ->5->3->4          1    0    1          7 0
         3          5 ->3->4->5->3    ->5->3->4->5       1    1    1          8 1

8 rows selected.

Если вы раскомментируете фильтр с помощью cnt1/cnt2/cnt3 и удаляете "идентификатор цикла установлен равным 1 по умолчанию 0", тогда запрос вернет результат в виде соответствующего запроса выше. Другими словами, вы можете избежать cycle clause и реализовать любую логику обнаружения цикла, которую вы считаете более интуитивной.

Дополнительные сведения об обходе иерархий и обнаружении циклов можно найти в книге Oracle SQL Revealed.