Как изобразить ориентированный граф с несколькими родителями?

8

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html предоставляет алгоритм для вставки и удаления из таблицы закрытия.

Я хотел бы смоделировать подобную структуру данных, за исключением того, что у узлов может быть несколько родителей.

Данный:

График № 1

Если мы удалим, [B, C]я ожидаю, что в конечном итоге:

График № 2

и если мы удалим узел, Bя ожидаю, что в конечном итоге:

График № 3

Однако, если вы используете авторский алгоритм для удаления ссылок или узлов, вы заметите, что это теги [D, C, 1]для удаления, что нежелательно.

Что я пробовал до сих пор

Я попытался адаптировать исходную структуру данных, добавив referencesстолбец, в котором указано, сколько способов пройти между двумя узлами. В приведенном выше примере, вы можете путешествовать от Aдо Cили через Bили через D. Идея состояла в том, чтобы при Bудалении сохранялся путь от Aк Cи счетчик ссылок уменьшался с 2 до 1. Теоретически это было хорошо, но я не мог понять, как заставить реализацию работать, и теперь мне интересно, это вообще возможно (структура данных может не содержать достаточно информации, чтобы выяснить, какие строки удалить).

Что я спрашиваю

Как бы вы адаптировали Closes Tables для поддержки нескольких родителей? Какие альтернативные структуры данных вы бы порекомендовали? https://stackoverflow.com/q/4048151/14731 содержит исчерпывающий список таких структур данных, но не ясно, какие из них поддерживают (или лучше всего подходят) несколько родителей.

database-design hierarchy Гили
источник
Итак, что вы пробовали? А что это за referencesколонка?
ypercubeᵀᴹ
Я не верю, что можно было бы адаптировать таблицы закрытия в вашем сценарии. Таблицы замыкания хороши для многих древовидных приложений, но этот вопрос ссылается на гораздо менее строгий тип DAG (направленный ациклический граф). Это тема, которая может подойти для магистерской диссертации и, как и многие другие вещи, когда речь заходит о базах данных, оптимальное решение будет в значительной степени зависеть от вашего конкретного конкретного случая использования. Это или это может помочь вам начать.
Avarkx
Какое программное обеспечение БД?
Нил Макгиган
@NeilMcGuigan, H2 и PostgreSQL, хотя, очевидно, я предпочитаю решение, не зависящее от БД.
Гили

Ответы:

3

Обычно создают таблицу узлов и таблицу отношений. Направленные графы не являются действительно иерархическими, и у них могут быть циклы, что усложняет запрос. Но если вы думаете о DAG как об обобщенном дереве (т. Е. О дереве, допускающем несколько родителей, но все еще строго иерархически), и о ориентированном графе как об обобщенном DAG (то есть, как DAG, но не строго иерархически), то все становится проще.

Поэтому для очень простого решения PostgreSQL мы можем сделать что-то вроде:

CREATE TABLE node (
    id serial primary key,
    payload jsonb not null
);

CREATE TABLE relationship (
    id serial primary key,
    relationship_type text not null,
    from_node int references node(id) not null,
    to_node int references node(id) not null,
    payload jsonb not null
);

Затем вы можете запросить что-то вроде этого:

with recursive dg as (
    select n.id as node_id, null::Int as parent, array[n.id] as path
      from node n
    union all
    select to_node, from_node, path || to_node
      FROM relationship
      JOIN dg on dg.node_id = from_node AND NOT from_node = ANY(path)
)
select * from dg;
Крис Траверс
источник