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

Question

Oracle SQL может выполнять иерархические запросы с v2, используя свой собственный синтаксис CONNECT BY. В своем последнем релизе 11g 2 они добавили рекурсивный факторинг подзапроса, также известный как рекурсивный с предложением. Это стандарт 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 - основаны на значении.

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

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

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

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

PostgreSQL Реализация, с другой стороны, действительно установлена ​​на основе.

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

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

Update:

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

• SQL Server: are the recursive CTE’s really set-based?

Answer 2

Сервер MySQL версии 5.0.45 не нравится with:

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

Answer 3

AFAIK:

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

Answer 4

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

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

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 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)