Как сохранить дерево зависимостей в базе данных?

Question

Я пытаюсь сохранить дерево зависимостей в базе данных PostgreSQL. Существует около 20 000 программных элементов, каждый из которых может зависеть от нескольких других элементов.

Существует несколько типов зависимостей (некоторые - зависимости времени выполнения, некоторые - зависимости времени сборки, а некоторые - зависимости теста).

Зависимость является рекурсивной, и каждый элемент знает только о вещах, от которых он непосредственно зависит.

Мне нужно будет перечислить все зависимости элемента и отобразить их как в виде дерева, так и в виде плоского списка. Мне также нужно ответить «что зависит от этого предмета?»

Каков рекомендуемый способ хранения этой информации, чтобы сделать выборку относительно простой?

Answer 1

Возможно, стоит взять копию Джо Селко «Деревья и иерархии в SQL для умников». В нем есть объяснения и примеры различных опций, доступных для такого рода вещей.

Answer 2

Я бы сохранил данные в виде, подобном

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)
);

Вы сможете получить список всех зависимостей с чем-то вроде:

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;

Редактировать: чтобы получить дерево, хорошим способом является накопление зависимостей в формате ARRAY. Для каждого шага в рекурсии используйте оператор добавления массива (||), чтобы добавить новый идентификатор в массив и получить его в конце.

Answer 3

Я бы использовал ORM, построил граф объектов в памяти и затем позволил бы ORM сохранить его: P.

Answer 4

Я бы реализовал простое автоматическое отношение «многие ко многим».

Примерно так:

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