使用递归子查询因子进行循环检测

Question

自从v2以来,Oracle SQL可以使用其专有的CONNECT BY语法进行分层查询.在他们最新的11g版本2中,他们添加了递归子查询因子,也称为recursive with子句.这是ANSI标准,如果我理解正确,这个也已由其他RDBMS供应商实现.

将connect-by与递归with进行比较时,我注意到使用循环检测时结果集的差异.结果连接对我来说更直观,所以我想知道Oracle的实现是否包含错误,或者这是否是标准ANSI和预期行为.因此,我的问题是,如果您可以使用其他数据库(如MySQL,DB2,SQL Server等)检查递归查询.如果这些数据库当然支持recursive 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;

Answer 1

从文档CONNECT_BY_ISCYCLE:

该CONNECT_BY_ISCYCLE虚列返回1如果当前行有一个孩子,这也是它的祖先

那个CYCLE:

如果行的一个祖先行具有相同的循环列值,则认为该行形成循环.

在您的示例中,row 2确实有一个子节点,它也是它的祖先,但它id尚未返回.

换句话说,CONNECT_BY_ISCYCLE检查子项(尚未返回),同时CYCLE检查当前行(已返回).

CONNECT BY是基于行的,而递归是基于CTE集合的.

请注意,Oracle的文档CYCLE提到了"祖先行".但是,一般来说,在递归中没有"祖先行"的概念CTE.它是一个基于集合的操作,可以完全从树中产生结果.一般来说,锚点部分和递归部分甚至可以使用不同的表格.

由于递归CTE的是通常用于建立层次结构树,Oracle决定增加一个周期的检查.但由于递归CTE运行的基于集合的方式,通常不可能告诉下一步是否会生成一个循环,因为没有明确定义"祖先行"循环条件也无法定义.

要执行"下一步",整个"当前"集需要可用,但要生成当前集的每一行(包括循环列),我们只需要获得"下一步"操作的结果.

如果当前集合总是由单行(如in CONNECT BY)组成,则不是问题,但如果在整个集合上定义递归操作则会出现问题.

还没有深入研究Oracle 11,但是只需隐藏它们就可以SQL Server实现递归,这需要放置许多限制(所有限制都有效地禁止所有基于集合的操作).CTECONNECT BY

PostgreSQL另一方面,实现是真正基于集合的:您可以在递归部分中使用锚点部分进行任何操作.但是,它没有任何检测周期的方法,因为首先没有定义周期.

如前所述,MySQL根本没有实现CTE(它也没有实现HASH JOIN's或MERGE JOINs,只有嵌套循环,所以不要太惊讶).

具有讽刺意味的是,我今天收到了一封关于这个主题的信,我将在我的博客中介绍.

更新:

递归CTE的SQL Server只不过CONNECT BY是伪装.有关令人震惊的详细信息,请参阅我的博客中的这

• SQL Server:递归CTE是否真的基于集合？

Answer 2

PostgreSQL支持WITH样式的分层查询,但没有任何自动循环检测.这意味着您需要编写自己的行,并且返回的行数取决于您在查询的递归部分中指定连接条件的方式.

如果ID(称为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