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

Question

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

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;

677 5

sql oracle db2 hierarchical-query

5 ответов:

Comments

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

Quassnoi · Accepted Answer · 2009-11-19 16:41:08

Из документации по 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 замаскированы. Смотрите эту статью в моем блоге для шокирующих подробностей:

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

Aleksander Kmetec · Accepted Answer · 2009-11-14 03:06:56

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

Andomar · Accepted Answer · 2009-11-14 01:03:43

АФАИК:

MySQL не поддерживает рекурсивные CTE

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

wallyk · Accepted Answer · 2014-01-27 09:35:29

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

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

user3237729 · Accepted Answer · 2014-01-26 17:10:21

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)