Иерархический запрос для графа от факторинга подзапроса к оракулам `` 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

Однако мне хотелось бы, чтобы запрос использовал функцию Oracle 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

В чем проблема с моим запросом и как я могу исправить это, чтобы включить только необходимые строки?

В вашем запросе нет ничего плохого.Иерархический запрос учитывает ребра, поэтому, если вы включите столбец 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

Результаты :

| 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

Результаты :

| 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 |

Answer 2

Левый запрос на соединение не возвращает ожидаемый результат:

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 by1004 *

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

Теперь можно начать с родительского элемента как нулевого и подключить 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>