使用递归子查询因子分解的循环检测

Question

从v2开始，Oracle SQL就可以使用其专有的CONNECT BY语法执行分层查询。在其最新的11g第2版中，他们添加了递归子查询分解，也称为递归with子句。这是ANSI标准，如果我理解正确的话，其他RDBMS供应商也已经实现了这个标准。

在比较connect-by和递归with时，我注意到使用周期检测时结果集有所不同。connect by的结果对我来说更直观，所以我想知道Oracle的实现是否包含错误，或者这是否是标准ANSI和预期行为。因此，我的问题是，您是否可以使用其他数据库如MySQL、DB2、SQL Server和其他数据库来检查递归with查询。当然，前提是这些数据库支持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上

如果某一行的祖先行具有与循环列相同的值，则该行被视为形成循环。

在您的示例中，行2确实有一个子行，它也是它的祖先，但它的id尚未返回。

换句话说，CONNECT_BY_ISCYCLE检查子(尚未返回)，而CYCLE检查当前行(已经返回)。

CONNECT BY是基于行的，而递归CTE是基于集合的。

注意，Oracle关于CYCLE的文档提到了一个“祖先行”。但是，一般来说，在递归CTE中没有“祖先行”的概念。这是一个基于集合的操作，可以产生完全脱离树的结果。一般来说，锚部分和递归部分甚至可以使用不同的表。

由于递归CTE通常用于构建层次树，Oracle决定添加一个循环检查。但是由于递归CTE的基于集合的操作方式，通常不可能判断下一步是否会生成循环，因为如果没有明确的“祖先行”循环条件也无法定义。

要执行“下一步”，整个“当前”集合需要可用，但要生成当前集合的每一行(包括cycle列)，我们只需要“下一步”操作的结果。

如果当前集合总是由一行组成(就像在CONNECT BY中一样)，这不是问题，但如果递归操作定义在一个集合上作为一个整体，这就是问题。

我还没有研究过Oracle 11，但是SQL Server通过在递归CTE后面隐藏一个CONNECT BY来实现递归all，这需要设置许多限制(所有这些限制都有效地禁止了所有基于集合的操作)。

另一方面，PostgreSQL的实现是真正基于集合的:你可以对递归部分中的锚部分做任何操作，但是它没有任何方法来检测循环，因为循环一开始就没有定义。

正如前面提到的，MySQL根本不实现CTE(它也不实现HASH JOIN或MERGE JOIN，只实现嵌套循环，所以不要太惊讶)。

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

更新：

SQL Server中的递归CTE只不过是伪装的CONNECT BY，更多令人震惊的细节请参见我博客中的这篇文章：

Answer 2

PostgreSQL支持WITH风格的分层查询，但没有任何自动周期检测功能。这意味着您需要自己编写，返回的行数取决于您在查询的递归部分中指定联接条件的方式。

这两个示例都使用数组if if(称为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

Answer 3

AFAIK：

• MySQL不支持递归CTE的
• SQL Sever不支持递归CTE的

中的周期检测