使用递归子查询分解进行循环检测
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
Oracle SQL 从 v2 开始就可以使用其专有的 CONNECT BY 语法进行分层查询。在最新的 11g 第 2 版中，他们添加了递归子查询分解，也称为递归 with 子句。这是 ANSI 标准，如果我理解正确的话，其他 RDBMS 供应商也已经实现了这一标准。
当比较 connect-by 和 recursive 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;
解决方案
从文档 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 伪装的。请参阅我博客中的这篇文章，了解令人震惊的细节：
其他提示
的PostgreSQL WITH式支持层次化的查询，但不具有任何自动循环的检测。这意味着你需要编写自己和行数返回取决于您指定查询的递归部分连接条件的方式。
两个示例都使用阵列如果标识（称为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
AFAIK：
- MySQL 不支持递归 CTE
- SQL Sever 不支持循环 递归 CTE 中的检测
MySQL服务器版本5.0.45不喜欢with：
错误1064（42000）：你在你的SQL语法错误;检查 对应于您的MySQL服务器版本的权利手册 语法使用近“与TR（ID，PARENT_ID）为（选择ID，PARENT_ID 从吨其中id = 1个UNION 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）通过连接检测周期如果对于当前行的子ID 是其一部分 的ID访问迄今
（2）与REC检测周期，如果作为当前行ID 是ID的一部分 访问迄今
所述第二查询的结果看起来最自然虽然有附加谓词and prior id_parent is not null。在这种情况下
（3）在检测到循环，如果作为当前行ID 是<强>父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并删除“周期ID设定的周期为1个默认0”，则查询将返回结果作为上述对应的查询。换句话说的就可以避免cycle clause和实施你发现无论周期检测逻辑更直观
可以在书中找到有关遍历层级和周期检测的附加细节的Oracle SQL揭示
