Como representar um gráfico direcionado com vários pais?

8

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html fornece um algoritmo para inserir e excluir de uma tabela de fechamento.

Eu gostaria de modelar uma estrutura de dados semelhante, exceto que os nós podem ter vários pais.

Dado:

Gráfico # 1

Se removermos [B, C], espero terminar com:

Gráfico # 2

e se removermos o nó B, espero terminar com:

Gráfico # 3

No entanto, se você usar o algoritmo do autor para remover links ou nós, notará que ele marca [D, C, 1]para exclusão, o que é indesejável.

O que eu tentei até agora

Tentei adaptar a estrutura de dados original adicionando uma referencescoluna que indica quantas maneiras existem para viajar entre dois nós. No exemplo acima, você pode viajar de Apara Catravés Bou através D. A idéia seria que, quando Bremovida, o caminho de Apara Cé mantido e a contagem de referência diminui de 2 para 1. Foi legal em teoria, mas não consegui descobrir como fazer a implementação funcionar e agora me pergunto se é possível (a estrutura de dados pode não conter informações suficientes para descobrir quais linhas remover).

O que estou perguntando

Como você adaptaria as tabelas de fechamento para apoiar vários pais? Quais estruturas de dados alternativas você recomendaria? https://stackoverflow.com/q/4048151/14731 contém uma lista exaustiva dessas estruturas de dados, mas não está claro quais suportam (ou são melhores para) vários pais.

Gili
fonte
Então, o que você tentou? E qual é a referencescoluna?
precisa saber é o seguinte
Não acredito que alguém possa adaptar tabelas de fechamento no seu cenário. As tabelas de fechamento são boas para muitos aplicativos baseados em árvore, mas essa pergunta faz alusão a um tipo muito menos restritivo de DAG (Directed Acyclic Graph). Este é um tópico que pode ser adequado para uma tese de mestrado e, como muitas outras coisas no que diz respeito a bancos de dados, uma solução ideal depende muito do seu caso de uso específico e exato. Isso ou isso pode ajudar você a começar.
Avarkx
Qual software db?
Neil McGuigan
@ NeilMcGuigan, H2 e PostgreSQL, embora obviamente eu prefira uma solução independente de banco de dados.
Gili

Respostas:

3

Geralmente crie uma tabela de nós e uma tabela de relacionamentos. Os gráficos direcionados não são realmente hierárquicos e podem ter loops, o que dificulta a consulta. Mas se você pensa em um DAG como uma árvore generalizada (isto é, uma árvore que permite vários pais, mas ainda é estritamente hierárquica) e um gráfico direcionado como sendo um DAG generalizado (ou seja, como um DAG, mas não estritamente hierárquico), as coisas ficam mais fáceis.

Portanto, para uma solução PostgreSQL muito simples, podemos fazer algo como:

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

Então você pode consultar algo como isto:

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;
Chris Travers
fonte