如何表示具有多个父级的有向图？

Question

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html提供了一种用于从闭包表中插入和删除的算法。

我想建模一个类似的数据结构，除了节点可能有多个父节点。

鉴于：

如果我们删除[B, C]我希望最终得到：

如果我们删除节点，B我希望最终得到：

但是，如果您使用作者的算法删除链接或节点，您会注意到它标记[D, C, 1]为删除，这是不可取的。

到目前为止我尝试过的

我尝试通过添加一references列来调整原始数据结构，该列指示在两个节点之间有多少种方式可以传输。在上面的示例中，您可以从A到C通过B或通过D。这个想法本来是当B被删除时，从A到的路径C被保留并且引用计数从 2 减少到 1。理论上这很好，但我不知道如何让实现工作，现在我想知道这是完全可能的（数据结构可能没有包含足够的信息来确定要删除哪些行）。

我在问什么

您将如何调整 Closure Tables 以支持多个父母？您会推荐哪些替代数据结构？/sf/ask/283370601/包含此类数据结构的详尽列表，但尚不清楚哪些支持（或最适合）多个父级。

Answer 1

通常创建一个节点表和一个关系表。有向图并不是真正的分层结构，它们可能有循环，这使得查询变得更加困难。但是，如果您将 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;