How to store dependency tree in a database?

Question

I am trying to store a dependency tree in a PostgreSQL database. There are about 20,000 software items, each item can depend on several other items.

There are several types of dependencies (some are run-time dependencies, some are build-time dependencies and some are test-dependencies).

The dependency is recursive and each item only knows about the things it immediately depends on.

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

What would be a recommended way to store this information to make fetching relatively easy?

Answer 1

I'd implement a simple many-to-many auto relationship.

Something like this:

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

Answer 2

I would use an ORM, construct the object graph in memory and then let the ORM to persist it :P.

Answer 3

It might be worth picking up a copy of Joe Celko's "Trees and Hierarchies in SQL for Smarties". It has a explanations and examples of the different options available for this sort of thing.

Answer 4

I'd store 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'll be able to 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 the dependencies in ARRAY format. For each step in the recursion use the array append operator (||) to add the new ID to an array, and get it out at the end.