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



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

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

Вот как это работает на 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;
215   5  

5 ответов:

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

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

И что дальше CYCLE:

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

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

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

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

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

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

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

PostgreSQL'реализация s, с другой стороны, действительно основана на множестве.

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

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

Обновление:

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

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

Оба примера используют массив if IDs (называемый 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

АФАИК:

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

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

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

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)

    Ничего не найдено.

Добавить ответ:
Отменить.