How to save a dependency tree in a database?

Question

I am trying to save a dependency tree in a PostgreSQL database. There are about 20,000 program elements, each element may depend on several other elements.

There are several types of dependencies (some of them depend on runtime, some of them depend on build time, and some on test dependencies).

Dependency is recursive, and each element knows only about what it directly depends on.

I will need to list all the dependencies of the element and display them both as a tree and as a flattened list. I also need to answer "what depends on this element?"

What would be the recommended way to store this information to make sampling relatively easy?

Answer 1

It might be worth collecting a copy of Joe Selco's Trees and Hierarchies in SQL for Smarties. It has explanations and examples of the various options available for this kind of thing.

Answer 2

I would save the data in something like

CREATE TABLE software ( id SERIAL PRIMARY KEY, ... ); CREATE TABLE software_dependency ( dependent int NOT NULL REFERENCES software(id), dependee int NOT NULL REFERENCES software(id), deptype int, -- or whatever you want CONSTRAINT pk_software_dependency PRIMARY KEY (dependent, dependee) ); 

You can get a list of all the dependencies with something like:

 WITH RECURSIVE t(id,type) AS ( SELECT dependee,deptype FROM software_dependency WHERE dependent=3 UNION ALL SELECT d.dependee,deptype FROM software_dependency d INNER JOIN t ON t.id=d.dependent ) SELECT * FROM t; 

Edit: to get a tree, a good way is to accumulate dependencies in the ARRAY format. For each step in recursion, use the append operator (||) array to add a new identifier to the array and get it at the end.

Answer 3

I would apply an automatic many-to-many relationship.

Something like that:

  Software Dependency +------------+ +-----------------------+ | SoftwareId | | SoftwareId | +------------+ /| DependsUponSoftwareId | | Name |--------|-+-----------------------+ | ... | \| ... | +------------+ +-----------------------+ 

Answer 4

I would use ORM, plot the object graph in memory, and then let ORM persist: P.