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

Question

Oracle SQL может выполнять иерархические запросы начиная с v2, используя их собственный синтаксис CONNECT BY. В своем последнем выпуске 11g 2 они добавили рекурсивный факторинг подзапросов, также известный как рекурсивный оператор with. Это стандарт ANSI, и, если я правильно понимаю, он был реализован и другими поставщиками СУБД.

При сравнении соединения с рекурсивом с, я заметил разницу в наборе результатов при использовании обнаружения цикла. Соединение по результатам для меня более интуитивно понятно, поэтому мне интересно, содержит ли реализация Oracle ошибку, или это стандарт ANSI и ожидаемое поведение. Поэтому мой вопрос, можете ли вы проверить рекурсив с помощью запроса, используя другие базы данных, такие как MySQL, DB2, SQL Server и другие. При условии, что эти базы данных поддерживают рекурсивную оговорку с условием.

Вот как это работает в Oracle 11.2.0.1.0

SQL> select *
  2    from t
  3  /

        ID  PARENT_ID
---------- ----------
         1          2
         2          1

2 rows selected.

Запрос с использованием синтаксиса CONNECT BY:

SQL>  select id
  2        , parent_id
  3        , connect_by_iscycle
  4     from t
  5  connect by nocycle parent_id = prior id
  6    start with id = 1
  7  /

        ID  PARENT_ID CONNECT_BY_ISCYCLE
---------- ---------- ------------------
         1          2                  0
         2          1                  1

2 rows selected.

Что выглядит для меня интуитивно понятным. Однако, используя новый синтаксис ANSI, он возвращает еще одну строку:

SQL> with tr (id,parent_id) as
  2  ( select id
  3         , parent_id
  4      from t
  5     where id = 1
  6     union all
  7    select t.id
  8         , t.parent_id
  9      from t
 10           join tr on t.parent_id = tr.id
 11  ) cycle id set is_cycle to '1' default '0'
 12  select id
 13       , parent_id
 14       , is_cycle
 15    from tr
 16  /

        ID  PARENT_ID I
---------- ---------- -
         1          2 0
         2          1 0
         1          2 1

3 rows selected.

Это скрипт, который вы можете использовать для проверки:

create table t
( id        number
, parent_id number
);
insert into t values (1, 2);
insert into t values (2, 1);
commit;
with tr (id,parent_id) as
( select id
       , parent_id
    from t
   where id = 1
   union all
  select t.id
       , t.parent_id
    from t
         join tr on t.parent_id = tr.id
) cycle id set is_cycle to '1' default '0'
select id
     , parent_id
     , is_cycle
  from tr;

Answer 1

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

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

и что на CYCLE:

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

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

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

CONNECT BY основано на строках, а рекурсивные 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 основан на множествах?

Answer 2

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

В обоих примерах для определения циклов используются массивы if (называемые 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

Answer 3

AFAIK:

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

Answer 4

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

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

Answer 5

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

Ниже запросы демонстрируют различные подходы для обнаружения циклов, начинающихся с 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 с обнаруживает цикл, если ID для текущей строки является частью идентификаторов Посетил до сих пор

Результат второго запроса выглядит наиболее естественным, хотя есть дополнительный предикат 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 .

Answer 6

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)