How to store dependency tree in a database?

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开发者_JAVA百科 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?

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.

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.

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

Something like this:

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

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