Найти родителя рекурсивно, используя запрос

Question

Я использую postgresql. У меня есть таблица как таковая ниже

parent_id child_id 
---------------------- 
101  102 
103  104 
104  105 
105  106 

Я хочу написать sql-запрос, который даст конечный родительский элемент ввода.

т.е. предположим, я передать 106 в качестве входных данных, то его выходной сигнал будет 103.

(106 --> 105 --> 104 --> 103) 

Answer 1

Вот полный пример. Сначала DDL:

test=> CREATE TABLE node (
test(> id SERIAL, 
test(> label TEXT NOT NULL, -- name of the node 
test(> parent_id INT, 
test(> PRIMARY KEY(id) 
test(>); 
NOTICE: CREATE TABLE will create implicit sequence "node_id_seq" for serial column "node.id" 
NOTICE: CREATE TABLE/PRIMARY KEY will create implicit index "node_pkey" for table "node" 
CREATE TABLE 

... и некоторые данные ...

test=> INSERT INTO node (label, parent_id) VALUES ('n1',NULL),('n2',1),('n3',2),('n4',3); 
INSERT 0 4 
test=> INSERT INTO node (label) VALUES ('garbage1'),('garbage2'), ('garbage3'); 
INSERT 0 3 
test=> INSERT INTO node (label,parent_id) VALUES ('garbage4',6); 
INSERT 0 1 
test=> SELECT * FROM node; 
id | label | parent_id 
----+----------+----------- 
1 | n1  |   
2 | n2  |   1 
3 | n3  |   2 
4 | n4  |   3 
5 | garbage1 |   
6 | garbage2 |   
7 | garbage3 |   
8 | garbage4 |   6 
(8 rows) 

Это выполняет рекурсивный запрос на каждый идентификатор в узле:

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path 
FROM node AS tn 
WHERE tn.parent_id IS NULL 
UNION ALL 
SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, 
     (p.path || '->' || c.id::TEXT) 
FROM nodes_cte AS p, node AS c 
WHERE c.parent_id = p.id 
) 
SELECT * FROM nodes_cte AS n ORDER BY n.id ASC; 
id | label | parent_id | depth | path  
----+----------+-----------+-------+------------ 
1 | n1  |   |  1 | 1 
2 | n2  |   1 |  2 | 1->2 
3 | n3  |   2 |  3 | 1->2->3 
4 | n4  |   3 |  4 | 1->2->3->4 
5 | garbage1 |   |  1 | 5 
6 | garbage2 |   |  1 | 6 
7 | garbage3 |   |  1 | 7 
8 | garbage4 |   6 |  2 | 6->8 
(8 rows) 

Это получает все потомки WHERE node.id = 1:

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path FROM node AS tn WHERE tn.id = 1 
UNION ALL     
SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, (p.path || '->' || c.id::TEXT) FROM nodes_cte AS p, node AS c WHERE c.parent_id = p.id 
)                 
SELECT * FROM nodes_cte AS n; 
id | label | parent_id | depth | path  
----+-------+-----------+-------+------------ 
1 | n1 |   |  1 | 1 
2 | n2 |   1 |  2 | 1->2 
3 | n3 |   2 |  3 | 1->2->3 
4 | n4 |   3 |  4 | 1->2->3->4 
(4 rows) 

Ниже будет получить путь узла с идентификатором 4:

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path 
FROM node AS tn 
WHERE tn.parent_id IS NULL 
UNION ALL 
SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, 
     (p.path || '->' || c.id::TEXT) 
FROM nodes_cte AS p, node AS c 
WHERE c.parent_id = p.id 
) 
SELECT * FROM nodes_cte AS n WHERE n.id = 4; 
id | label | parent_id | depth | path  
----+-------+-----------+-------+------------ 
4 | n4 |   3 |  4 | 1->2->3->4 
(1 row) 

И давайте предположим, что вы хотите ограничить поиск потомков с depth менее трех (обратите внимание, что depth еще не увеличивается):

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
    SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path 
    FROM node AS tn WHERE tn.id = 1 
UNION ALL 
    SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, 
     (p.path || '->' || c.id::TEXT) 
    FROM nodes_cte AS p, node AS c 
    WHERE c.parent_id = p.id AND p.depth < 2 
) 
SELECT * FROM nodes_cte AS n; 
id | label | parent_id | depth | path 
----+-------+-----------+-------+------ 
    1 | n1 |   |  1 | 1 
    2 | n2 |   1 |  2 | 1->2 
(2 rows) 

Я бы рекомендовал использовать тип данных ARRAY вместо строки для демонстрации «путь», но стрелка нагляднее родителя < => ребенок отношения.

Answer 2

Используйте команду WITH RECURSIVE, чтобы создать общее выражение таблицы (CTE). Для нерекурсивен срока, получить строки, в которых ребенок находится непосредственно под родителем:

SELECT 
    c.child_id, 
    c.parent_id 
FROM 
    mytable c 
LEFT JOIN 
    mytable p ON c.parent_id = p.child_id 
WHERE 
    p.child_id IS NULL 

child_id | parent_id 
----------+----------- 
     102 |  101 
     104 |  103 

Для рекурсивного термина, вы хотите ребенок этих детей.

WITH RECURSIVE tree(child, root) AS (
    SELECT 
     c.child_id, 
     c.parent_id 
    FROM 
     mytable c 
    LEFT JOIN 
     mytable p ON c.parent_id = p.child_id 
    WHERE 
     p.child_id IS NULL 
    UNION 
    SELECT 
     child_id, 
     root 
    FROM 
     tree 
    INNER JOIN 
     mytable on tree.child = mytable.parent_id 
) 
SELECT * FROM tree; 

child | root 
-------+------ 
    102 | 101 
    104 | 103 
    105 | 103 
    106 | 103 

Вы можете отфильтровать детей при запросе КТР:

WITH RECURSIVE tree(child, root) AS (...) SELECT root FROM tree WHERE child = 106; 

root 
------ 
    103