从邻接表中将元素的祖先写入 Postgres table

Question

我想将作为邻接列表存储的 1 到 n 层次结构写入 table，其中列出了每个元素的祖先。我正在使用 Postgres 数据库（Postgres 10，但要部署代码的机器运行 Postgres 9.x）。

样本输入table（邻接表）：

INSERT INTO public.test (id, name, parent_id)
VALUES (1, 't', 1),
   (11, 't1', 1),
   (12, 't2', 1),
   (13, 't3', 1),
   (111, 't11', 11),
   (112, 't12', 11),
   (121, 't21', 12),
   (14, 't4', 1),
   (141, 't41', 14),
   (142, 't42', 14)

因此，我想要一个看起来像这样的 table（只显示了几行；此外，我试图解决的现实生活问题有七个层级，而不是只有两个） :

+-----+-------+--------+--------+
| id  | level | level0 | level1 |
+-----+-------+--------+--------+
|   1 |     0 | NULL   | NULL   |
|  11 |     1 | 1      | NULL   |
|  12 |     1 | 1      | NULL   |
| 111 |     2 | 1      | 11     |
+-----+-------+--------+--------+

id 是元素的 id，level 是该元素在层次结构中的级别（0 是根级别），level0/1 是元素的祖先各自的等级。

我是 SQL 的新手，所以我没有任何代码可以向您展示。谷歌搜索告诉我，我可能需要使用递归 CTE 来获得所需的结果并执行自连接，但我一直无法弄清楚如何去做。感谢您的帮助。

编辑

这是我目前尝试过的方法：

WITH RECURSIVE cte AS
(
SELECT m.id AS id,
    0 AS level,
    m.parent_id AS level0,
    m.parent_id AS level1,
    m.parent_id AS parent
    FROM public.test AS m
    WHERE m.parent_id IS NULL

UNION ALL

SELECT 
    m.id,
    cte.level + 1,
    cte.parent AS level0,
    cte.parent AS level1,
    m.parent_id AS parent
    FROM public.test AS m 
        INNER JOIN cte
            ON m.parent_id = cte.id 
)
SELECT *
FROM cte;

当然，将 level0 和 level1 设置为元素的父元素不会产生预期的结果，但我不得不将其设置为某些东西并且没有比这更进一步的了。

Answer 1

如果对象的位置没有及时改变（即如果它从一开始就放在第 6 层，它将永远停留在该层）你可以引入一些 7 个数字的理智 ID，显示 7 个级别，用分号(:):

分隔

'1:1:1:1:1:1:1'

然后介绍一些功能指标，比如：

CREATE INDEX level1_idx ON main_table USING (regexp_split_to_array(id, '\:')[1])
CREATE INDEX level2_idx ON main_table USING (regexp_split_to_array(id, '\:')[2])
CREATE INDEX level3_idx ON main_table USING (regexp_split_to_array(id, '\:')[3])

那么你总是可以进行高效的查询：

SELECT id, regexp_split_to_array(id, '\:')[1] as level1, regexp_split_to_array(id, '\:')[2] as level2, ...
ORDER BY level1, level2, level3 ...

Answer 2

SQL 是一种严格类型的语言，它不允许从 SELECT 返回的列数根据它所作用的数据而变化。参见例如Split comma separated column data into additional columns 进行讨论。

但是，PostgreSQL 为您提供了一个 array type，您可以使用它来将动态大小的值收集到单个列中。以下递归 CTE 将每一行的所有祖先收集到这样的数组中：

with recursive rec(id, level, parent_id, ancestors) as (
  select id, 0, parent_id, array[] :: int[]
  from test
  where parent_id = id
  union all
  select t.id, rec.level + 1, t.parent_id, rec.ancestors || array[t.parent_id]
  from test t
  join rec on t.parent_id = rec.id
  where t.parent_id <> t.id
)
select 
  rec.id,
  rec.level,
  rec.ancestors
from rec;

如果级别有已知限制，您可以 select 每列数组中的元素：

select
  rec.id,
  rec.level,
  rec.ancestors[1] level1,
  rec.ancestors[2] level2,
  ...

SQL Fiddle

从邻接表中将元素的祖先写入 Postgres table

Write element's ancestry to Postgres table from adjacency list

sql

postgresql

recursive-query

hierarchical-data