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

Question

I'm having the following relation: A package has multiple 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)
);

A version has multiple dependencies. Those dependencies are again versions of other packages.

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

Take the npm registry for example from the JavaScript/Node.js ecosystem. You can generate a dependency tree using the following command.

npm list --prod

That lists all production dependencies.

├─┬ 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

As you can see in the example react-router-dom@5.2.0 depends on history@4.10.1 which depends on loose-envify@1.4.0.

The idea is to have all packages and their versions in a database and to find a query that lists all dependencies for a given package. I'd like to find the query that (more or less) gives me the following result.

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

I created a little sql fiddle with some dummy data that can be used as a playground - http://sqlfiddle.com/#!17/633dd.

I think recursive common table expressions are the way to go but I'm a bit lost since I haven't used them yet. I found the typical example where people have managers and you're able generate the organization chart but I wasn't able to transfer this to my problem.

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

Thank you very much for your help!

Answer 1

Below is a cte which produces all the dependences for a package (in this case the package with a version_id of 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;

See demo here.