24

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

在将连接方式与递归方式进行比较时，我注意到使用循环检测时结果集有所不同。按结果连接对我来说更直观，所以我想知道 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;
4

7 回答 7

15

从文档CONNECT_BY_ISCYCLE：

如果当前行有一个子元素，它也是它的祖先，则伪CONNECT_BY_ISCYCLE列返回1

和那个CYCLE：

如果其祖先行之一具有与循环列相同的值，则认为该行形成了一个循环。

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

换句话说，CONNECT_BY_ISCYCLE检查子项（尚未返回），同时CYCLE检查当前行（已返回）。

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

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

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

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

如果当前集合总是由单行组成（如 in CONNECT BY），这不是问题，但如果在整个集合上定义的递归操作是一个问题。

还没有研究Oracle 11，但只是通过隐藏 a来SQL Server实现递归，这需要放置许多限制（所有这些都有效地禁止所有基于集合的操作）。CTECONNECT BY

PostgreSQL另一方面，它的实现是真正基于集合的：你可以在递归部分对锚部分进行任何操作。但是，它没有任何方法可以检测周期，因为周期一开始就没有定义。

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

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

更新：

RecursiveCTE的 inSQL Server只不过CONNECT BY是伪装而已。有关令人震惊的细节，请参阅我博客中的这篇文章：

于 2009-11-18T18:02:20.733 回答
6

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

这两个示例都使用数组 if 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
于 2009-11-14T01:06:56.557 回答
3

AFAIK：

  • MySQL 不支持递归 CTE
  • SQL Sever 不支持递归 CTE 中的循环检测
于 2009-11-13T23:03:43.997 回答
1

MySQL 服务器版本 5.0.45 不喜欢with：

ERROR 1064 (42000)：您的 SQL 语法有错误；检查与您的 MySQL 服务器版本相对应的手册以获取正确的语法，以便在第 1 行的 'with tr (id, parent_id) as (select id, parent_id from t where id = 1 union all s' 附近使用。

于 2009-11-13T21:08:50.603 回答
1

连接方式的结果可能并不总是直观的。

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)。同时 edge (5, 3) 出现在第三次查询和第二次循环的结果中两次。

为什么这样？您可以在 Quassnoi 提供的答案中检查循环检测逻辑的描述。用简单的英语来说，它的意思是

(1) 如果当前行的子 ID是迄今为止访问的 ID 的一部分，则 connect by 检测循环

(2) 如果当前行的 ID 是迄今为止访问过的 ID 的一部分，rec with 会检测到一个循环

尽管有额外的谓词，但第二个查询的结果看起来最自然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 过滤并删除“cycle id set cycle to 1 default 0”，则查询将返回上述相应查询的结果。换句话说，您可以避免cycle clause并实施您认为更直观的任何循环检测逻辑。

有关遍历层次结构和循环检测的更多详细信息，请参阅Oracle SQL Revealed一书。

于 2018-11-20T22:25:39.550 回答
0 
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)

于 2014-01-26T14:50:25.037 回答
0

“因此我的问题是你是否可以使用 MySQL、DB2、SQL Server 等其他数据库来检查递归查询”

MariaDB 10.5.2 和更新版本支持循环检测：

和

CYCLE 子句启用 CTE 循环检测，避免过多或无限循环，MariaDB 支持宽松的非标准语法。

WITH RECURSIVE ... (
 ...
)
CYCLE <cycle column list> RESTRICT

例子：

CREATE TABLE t(id INT, parent_id INT);
INSERT INTO t(id, parent_id) VALUES (1, NULL),(2,1),(3,2),(1,3);

WITH RECURSIVE cte AS (
  SELECT id, parent_id, 0 lvl 
  FROM t WHERE parent_id IS NULL
  UNION ALL
  SELECT t.id, t.parent_id, lvl + 1 AS lvl
  FROM cte c1
  JOIN t ON c1.id = t.parent_id
)
CYCLE id, parent_id RESTRICT 
SELECT * FROM cte ORDER BY lvl;

db<>小提琴演示

于 2020-06-28T12:20:13.853 回答