从子查询分解到 Oracles ``connect by`` 的图形分层查询

Question

我有一个简单的有向图结构作为表的形式：

CREATE TABLE node (id NUMBER(8, 0), NAME VARCHAR2(100));
CREATE TABLE edge (parent NUMBER(8, 0), child NUMBER(8, 0));

其中 node 存储所有节点和 edge 从 parent 到 child 的所有有向边。我现在想要的是一个视图，显示从所有根（没有传入边的节点）到图中所有其他节点（包括零长度路径）的所有路径。该图保证没有循环。

我使用了一个使用子查询分解的分层查询，结果是这样的：

WITH rec_view(id, parent, lvl, root_id, path) AS (
    SELECT
        id
        , NULL
        , 1 lvl
        , id root_id
        , '/' || TO_CHAR(id) path
    FROM node g
    WHERE NOT EXISTS (SELECT 1 FROM edge h WHERE h.child = g.id)
    UNION ALL
    SELECT
        hier.child
        , prev.id
        , prev.lvl + 1 lvl
        , prev.root_id
        , prev.path || '/' || hier.child path
    FROM rec_view prev
        JOIN edge hier ON prev.id = hier.parent 
)
SELECT
    n.id, n.NAME, v.root_id, v.lvl, v.path
FROM
    rec_view v
    JOIN node n ON v.id = n.id

有了这个测试数据，我得到了 10 行的预期结果。

INSERT INTO node VALUES (1, 'KBR');
INSERT INTO node VALUES (2, 'H');
INSERT INTO node VALUES (3, 'N');
INSERT INTO node VALUES (4, 'KBR H');
INSERT INTO node VALUES (5, 'KBR N');
INSERT INTO node VALUES (6, 'Dummy');
INSERT INTO node VALUES (7, 'Nach H');

INSERT INTO edge VALUES (1, 4);
INSERT INTO edge VALUES (1, 5);
INSERT INTO edge VALUES (2, 4);
INSERT INTO edge VALUES (3, 5);
INSERT INTO edge VALUES (4, 7);

ID  Name   Root  Level    Path
------------------------------
1   KBR       1      1      /1
2   H         2      1      /2
3   N         3      1      /3
4   KBR H     1      2    /1/4
4   KBR H     2      2    /2/4
5   KBR N     1      2    /1/5
5   KBR N     3      2    /3/5
6   Dummy     6      1      /6
7   Nach H    2      3  /2/4/7
7   Nach H    1      3  /1/4/7

但是，我想要的是一个使用 Oracles CONNECT BY 特性的查询，因为我认为它比分解一的子查询更容易阅读和理解，它也是分层查询的首选方式在我们公司。但是我提出的查询导致我得到了太多结果。我得到的是：

SELECT
    parent.id id
    , parent.NAME NAME
    , connect_by_root parent.NAME root_id
    , LEVEL lvl
    , sys_connect_by_path(parent.id, '/') path
FROM
    node parent
    LEFT JOIN edge hier ON parent.id = hier.parent
START WITH
    NOT EXISTS (SELECT 1 FROM edge h WHERE h.child = parent.id)
CONNECT BY
    PRIOR hier.child = parent.id

这里我得到 11 行，而不是 10 行，路径为 /1 的行被包含两次。

ID  Name    Root  Level    Path
-------------------------------
1   KBR        1      1      /1
4   KBR H      1      2    /1/4
7   Nach H     1      3  /1/4/7
1   KBR        1      1      /1
5   KBR N      1      2    /1/5
2   H          2      1      /2
4   KBR H      2      2    /2/4
7   Nach H     2      3  /2/4/7
3   N          3      1      /3
5   KBR N      3      2    /3/5
6   Dummy      6      1      /6

我的查询有什么问题，如何解决这个问题以仅包含所需的行？

Answer 1

左连接查询未按预期返回结果：

SQL> SELECT *
  2  FROM
  3      node parent
  4      LEFT JOIN edge hier ON parent.id = hier.parent  ;
       ID NAME                                                                                PARENT     CHILD
--------- -------------------------------------------------------------------------------- --------- ---------
        1 KBR                                                                                      1         4
        1 KBR                                                                                      1         5
        2 H                                                                                        2         4
        3 N                                                                                        3         5
        4 KBR H                                                                                    4         7
        6 Dummy                                                                                      
        7 Nach H                                                                                     
        5 KBR N                                                                                      
8 rows selected

Parent.id 应该加入 heir.child 以使结果具有正确的形状，可以与 connect by clause

一起使用

SQL> SELECT *
  2  FROM
  3      node parent
  4      LEFT JOIN edge hier ON parent.id = hier.child  ;
       ID NAME                                                                                PARENT     CHILD
--------- -------------------------------------------------------------------------------- --------- ---------
        4 KBR H                                                                                    1         4
        5 KBR N                                                                                    1         5
        4 KBR H                                                                                    2         4
        5 KBR N                                                                                    3         5
        7 Nach H                                                                                   4         7
        6 Dummy                                                                                      
        1 KBR                                                                                        
        2 H                                                                                          
        3 N                                                                                          
9 rows selected

现在，可以在父级为 null 的情况下开始，并将 heir.parent 连接到 parent.id 的优先级以获得正确的层次结构

SQL> column name format a20
SQL> column root_id format a10
SQL> column path format a10
SQL> 
SQL> SELECT
  2      parent.id id
  3      , parent.NAME NAME
  4      , connect_by_root parent.NAME root_id
  5      , LEVEL lvl
  6      , sys_connect_by_path(parent.id, '/') path
  7  FROM
  8      node parent
  9      LEFT JOIN edge hier ON parent.id = hier.child
 10  START WITH
 11      PARENT IS NULL
 12  CONNECT BY
 13      hier.parent = PRIOR parent.id;
       ID NAME                 ROOT_ID           LVL PATH
--------- -------------------- ---------- ---------- ----------
        1 KBR                  KBR                 1 /1
        4 KBR H                KBR                 2 /1/4
        7 Nach H               KBR                 3 /1/4/7
        5 KBR N                KBR                 2 /1/5
        2 H                    H                   1 /2
        4 KBR H                H                   2 /2/4
        7 Nach H               H                   3 /2/4/7
        3 N                    N                   1 /3
        5 KBR N                N                   2 /3/5
        6 Dummy                Dummy               1 /6
10 rows selected

SQL>

Answer 2

What is the problem with my query and how can I fix this to only include the required rows?

您的查询没有问题。分层查询正在考虑边缘，因此如果您包含 child 列，您将看到 id = 1:

行的差异

SQL Fiddle

查询 1:

SELECT parent.id id
     , parent.NAME NAME
     , connect_by_root parent.NAME root_id
     , LEVEL lvl
     , sys_connect_by_path(parent.id, '/') path
     , child
FROM   node parent
       LEFT JOIN edge hier
       ON parent.id = hier.parent
START WITH
    NOT EXISTS (SELECT 1 FROM edge h WHERE h.child = parent.id)
CONNECT BY
    PRIOR hier.child = parent.id

Results:

| ID |   NAME | ROOT_ID | LVL |   PATH |  CHILD |
|----|--------|---------|-----|--------|--------|
|  1 |    KBR |     KBR |   1 |     /1 |      4 |
...
|  1 |    KBR |     KBR |   1 |     /1 |      5 |
...

行不同，因为它们具有不同的子边。

如果您只想获得不同的行，请添加 DISTINCT 关键字。

查询 2:

SELECT DISTINCT
       parent.id id
     , parent.NAME NAME
     , connect_by_root parent.NAME root_id
     , LEVEL lvl
     , sys_connect_by_path(parent.id, '/') path
FROM   node parent
       LEFT JOIN edge hier
       ON parent.id = hier.parent
START WITH
    NOT EXISTS (SELECT 1 FROM edge h WHERE h.child = parent.id)
CONNECT BY
    PRIOR hier.child = parent.id

Results:

| ID |   NAME | ROOT_ID | LVL |   PATH |
|----|--------|---------|-----|--------|
|  2 |      H |       H |   1 |     /2 |
|  7 | Nach H |       H |   3 | /2/4/7 |
|  4 |  KBR H |       H |   2 |   /2/4 |
|  4 |  KBR H |     KBR |   2 |   /1/4 |
|  7 | Nach H |     KBR |   3 | /1/4/7 |
|  5 |  KBR N |     KBR |   2 |   /1/5 |
|  1 |    KBR |     KBR |   1 |     /1 |
|  3 |      N |       N |   1 |     /3 |
|  5 |  KBR N |       N |   2 |   /3/5 |
|  6 |  Dummy |   Dummy |   1 |     /6 |

从子查询分解到 Oracles ``connect by`` 的图形分层查询

Hierarchical query for graph from subquery factoring to Oracles ``connect by``

sql

oracle

hierarchy