Обнаружение цикла с рекурсивным подразделением
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Oracle SQL может выполнять иерархические запросы со времен V2, используя их запатентованную связь с помощью синтаксиса. В своем последнем 11G -выпуске 2 они добавили рекурсивный подраздел под подразделением, также известный как рекурсивный с пунктом. Это стандарт ANSI, и если я правильно понимаю, этот также был реализован и другие поставщики RDBMS.
Сравнивая подключение с рекурсивным, я заметил разницу в наборе результатов при использовании обнаружения цикла. Результаты Connect By более интуитивно понятны, поэтому мне интересно, содержит ли реализация Oracle ошибка или это стандартное ANSI и ожидаемое поведение. Поэтому мой вопрос заключается в том, можно ли проверить рекурсив с помощью запроса, используя другие базы данных, такие как MySQL, DB2, SQL Server и другие. При условии, что эти базы данных подтверждают рекурсив с Clause, конечно.
Вот как это работает на Oracle 11.2.0.1.0
SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.
Запрос с использованием Connect By Syntax:
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;
Решение
Из документации на CONNECT_BY_ISCYCLE:
А
CONNECT_BY_ISCYCLEПсевдоколоновый возврат1Если в нынешнем ряду есть ребенок, который также является его предком
И это на CYCLE:
Считается, что строка образует цикл, если один из его предков имеет одинаковые значения для столбцов цикла.
В вашем примере ряд 2 есть ребенок, который также является его предком, но его id еще не был возвращен.
Другими словами, CONNECT_BY_ISCYCLE проверяет дети (которые еще не возвращены), пока CYCLE проверяет Текущий ряд (который уже возвращен).
CONNECT BY на основе ряда, в то время как рекурсивный CTEs основаны на основе.
Обратите внимание, что документация Oracle на CYCLE упоминает «ряд предка». Однако, вообще говоря, в рекурсивной рекурсии нет концепции «ряда предков» CTE. Анкет Это установленная операция, которая может дать результаты полностью из дерева. Вообще говоря, анкерная часть и рекурсивная часть могут даже использовать различные таблицы.
Поскольку рекурсивный CTE'есть обычно используется для строительства иерархических деревьев, Oracle решил добавить проверку цикла. Но из-за определения рекурсивного пути CTEРаботаю, как правило, невозможно сказать, что следующий шаг генерирует цикл или нет, потому что без четкого определения условия цикла «Ряд предков» также нельзя определить.
Чтобы выполнить шаг «следующий», должен быть весь набор «текущего», но для создания каждой строки текущего набора (который включает в себя столбец цикла), нам просто необходимо иметь результаты операции «Далее».
Это не проблема, если текущий набор всегда состоит из одной строки (например, в CONNECT BY), но это проблема, если рекурсивная операция, определенная в наборе в целом.
Не смотрел Oracle 11 пока, но SQL Server реализует рекурсивный CTE'просто скрывая CONNECT BY за ними, которые требуют размещения многочисленных ограничений (все из которых эффективно запрещают все наборные операции).
PostgreSQLРеализация, с другой стороны, действительно основана на основе: вы можете выполнить любую операцию с анкерной частью в рекурсивной части. Тем не менее, у него нет никаких средств для обнаружения циклов, потому что циклы не определены в первую очередь.
Как упоминалось ранее, MySQL не реализует CTEвообще (он не реализует HASH JOINs или MERGE JOINS также, только вложенные петли, так что не удивляйтесь многому).
По иронии судьбы, сегодня я получил письмо по этой теме, которое я расскажу в своем блоге.
Обновлять:
Рекурсивный CTEв SQL Server не более чем CONNECT BY замаскированный. Смотрите эту статью в моем блоге для шокирующих деталей:
Другие советы
PostgreSQL поддерживает иерархические запросы в стиле, но у него нет автоматического обнаружения цикла. Это означает, что вам нужно написать свои собственные, а количество возвращаемых строк зависит от того, как вы указываете условия соединения в рекурсивной части запроса.
Оба примера используют массив, если идентификаторы (называемые 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 SEAR не поддерживает обнаружение цикла в рекурсивном CTE
MySQL Server версия 5.0.45 не понравилась with:
Ошибка 1064 (42000): у вас есть ошибка в вашем синтаксисе SQL; Проверьте руководство, которое соответствует вашей версии MySQL Server для правильного синтаксиса для использования рядом с TR (ID, parent_id) как (выберите ID, parent_id из t, где id = 1 Союз All 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)
Результаты подключения могут не всегда быть интуитивно понятными.
Ниже запросов демонстрируют разные подходы к обнаружению циклов, начиная с 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) Подключите, обнаружив цикл, если идентификатор ребенка для текущего ряда является частью идентификаторов, посещаемых до сих пор
(2) rec с обнаружением цикла, если ID для текущего ряда является частью идентификаторов, посещаемых до сих пор
Результат второго запроса выглядит наиболее естественным, хотя есть дополнительный предикат and prior id_parent is not null. Анкет В таком случае
(3) Он обнаруживает цикл, если ID для текущего ряда это часть родительские идентификаторыпосещал до сих пор
Все эти условия реализованы в столбцах 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 раскрыл.
