使用查询递归查找父级

Question

我正在使用PostgreSQL数据库。我有一个如下所示的表格。

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

我想写一条SQL查询语句，可以给出输入的最终父级。

例如，假设我传递106作为输入，则输出将为103。

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

- Avadhesh

---

如果您正在使用Postgres，请删除SQL Server和Oracle标签。谢谢。 - Damian Leszczyński - Vash

linq-to-sql不支持postgresql，因此也删除了该标签。 - spender

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)

这会对node中的每个id执行递归查询：

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)

这将获取所有子节点，其中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)

以下代码将获取具有id 4的节点的路径： ```

以下代码将获取具有id 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)

假设你想将搜索限制为深度小于三的后代（注意，深度还没有增加）：

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数据类型来代替字符串来展示"路径", 但是箭头更能说明父子关系。

- Sean

---

这个方法在自身的多对多关系中可行吗？假设有一些节点有许多父节点，但是存在一个类似“子树ID”的字段，用于表示节点A仅是在此子树下的节点B的子节点，如果节点B在另一个子树中而A不在其中，则不会在B的下方显示A。我希望我表达清楚了我的目的！ - Vahid Alimohamadi

如何获取最后一个子节点的所有父节点？ - Washington Morais

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

在查询CTE时，您可以对子项进行筛选：

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

 root
------
  103

- xn.

---

这真的很优雅。它似乎是递归CTE的理想教学示例。因此，对于我的用例进行修改非常容易。 - Noumenon