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

Question

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

在比较 connect-by 和递归 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;

Answer 1

来自 CONNECT_BY_ISCYCLE 的文档:

The CONNECT_BY_ISCYCLE pseudocolumn returns 1 if the current row has a child which is also its ancestor

而在 CYCLE :

A row is considered to form a cycle if one of its ancestor rows has the same values for the cycle columns.

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

换句话说， CONNECT_BY_ISCYCLE检查 child (尚未归还)，而 CYCLE检查 当前行 (已经返回)。
CONNECT BY基于行，而递归 CTE是基于集合的。

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

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

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

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

没看 Oracle 11还没有，但是 SQL Server实现递归 CTE只是隐藏了一个 CONNECT BY在它们后面，这需要设置许多限制(所有这些限制都有效地禁止了所有基于集合的操作)。
PostgreSQL另一方面， 的实现是真正基于集合的:您可以对递归部分中的 anchor 部分进行任何操作。但是，它没有任何检测周期的方法，因为首先没有定义周期。

如前所述， MySQL不实现 CTE完全没有(它也没有实现 HASH JOIN 或 MERGE JOIN ，只有嵌套循环，所以不要感到惊讶)。

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

更新:

递归 CTE在 SQL Server不超过 CONNECT BY变相。有关令人震惊的详细信息，请参阅我博客中的这篇文章:

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