PostgreSQL：如何递归查找给定包的所有依赖项？

Question

我有以下关系：A package 有多个 versions.

CREATE TABLE IF NOT EXISTS package (
  id SERIAL PRIMARY KEY,
  name TEXT NOT NULL UNIQUE
);

CREATE TABLE IF NOT EXISTS version (
  id SERIAL PRIMARY KEY,
  package_id INT NOT NULL REFERENCES package,
  version TEXT NOT NULL,
  
  UNIQUE(package_id, version)
);

一个版本有多个dependencies。这些依赖项又是其他包的版本。

CREATE TABLE IF NOT EXISTS dependency (
  version_id INT NOT NULL REFERENCES version,
  dependency_id INT NOT NULL REFERENCES version
);

以 JavaScript/Node.js 生态系统中的 npm registry 为例。您可以使用以下命令生成依赖树。

npm list --prod

列出所有生产依赖项。

├─┬ react-router-dom@5.2.0
│ ├── @babel/runtime@7.13.17 deduped
│ ├─┬ history@4.10.1
│ │ ├── @babel/runtime@7.13.17 deduped
│ │ ├── loose-envify@1.4.0 deduped
│ │ ├── resolve-pathname@3.0.0
│ │ ├── tiny-invariant@1.1.0 deduped
│ │ ├── tiny-warning@1.0.3 deduped
│ │ └── value-equal@1.0.1
│ ├── loose-envify@1.4.0 deduped
│ ├─┬ prop-types@15.7.2
│ │ ├── loose-envify@1.4.0 deduped
│ │ ├── object-assign@4.1.1 deduped
│ │ └── react-is@16.13.1
│ ├─┬ react-router@5.2.0
│ │ ├── @babel/runtime@7.13.17 deduped
│ │ ├── history@4.10.1 deduped
│ │ ├── hoist-non-react-statics@3.3.2 deduped
│ │ ├── loose-envify@1.4.0 deduped
│ │ ├─┬ mini-create-react-context@0.4.1
│ │ │ ├── @babel/runtime@7.13.17 deduped
│ │ │ ├── prop-types@15.7.2 deduped
│ │ │ ├── react@17.0.2 deduped
│ │ │ └── tiny-warning@1.0.3 deduped
│ │ ├─┬ path-to-regexp@1.8.0
│ │ │ └── isarray@0.0.1
│ │ ├── prop-types@15.7.2 deduped
│ │ ├── react-is@16.13.1
│ │ ├── react@17.0.2 deduped
│ │ ├── tiny-invariant@1.1.0 deduped
│ │ └── tiny-warning@1.0.3 deduped
│ ├── react@17.0.2 deduped
│ ├── tiny-invariant@1.1.0
│ └── tiny-warning@1.0.3

如您在示例中所见，react-router-dom@5.2.0 取决于 history@4.10.1，而 history@4.10.1 又取决于 loose-envify@1.4.0。

我们的想法是将所有包及其版本存储在一个数据库中，并找到一个列出给定包的所有依赖项的查询。我想找到（或多或少）给我以下结果的查询。

| name             | version | level |
--------------------------------------
| react-router-dom | 5.2.0   | 1     |
| @babel/runtime   | 7.13.17 | 2     |
| history          | 4.10.1  | 2     |
| @babel/runtime   | 7.13.17 | 3     |
| loose-envify     | 1.4.0   | 3     |
| resolve-pathname | 3.0.0   | 3     |
| ...
| prop-types       | 15.7.2  | 2     |
| ...              | ...     | ...   |

我用一些虚拟数据创建了一个小 sql fiddle 可以用作游乐场 - http://sqlfiddle.com/#!17/633dd.

我认为递归通用 table 表达式是可行的方法，但我有点迷茫，因为我还没有使用过它们。我找到了一个典型的例子，其中人们有经理，你可以生成组织结构图，但我无法将其转移到我的问题中。

WITH RECURSIVE cte_name AS (
    CTE_query_definition -- non-recursive term
    UNION [ALL]
    CTE_query definion  -- recursive term
) SELECT * FROM cte_name;

非常感谢您的帮助！

Answer 1

下面是一个 cte，它产生一个包的所有依赖关系（在这种情况下，version_id 为 1 的包）：

with recursive cte(v_id, d_id, l) as (
   select d.*, 1 from dependency d where d.version_id = 1
   union all
   select case when d.version_id is null then c.d_id else d.version_id end, 
         case when d.dependency_id is null then null else d.dependency_id end, 
         c.l+1 
   from cte c left join dependency d on c.d_id = d.version_id where c.d_id  is not null
)
select v.package_id, p.name, v.version, c.l 
from cte c join version v on v.id = c.v_id join package p on p.id = v.package_id 
group by v.package_id, p.name, v.version, c.l
order by v.package_id;

查看演示 here。

PostgreSQL：如何递归查找给定包的所有依赖项？

PostgreSQL: How to find all dependencies recursively for a given package?

sql

database

postgresql

recursion

common-table-expression