database - 通过有向无环图存储唯一路径是否可行？

Question

客户端有一个存储为简单 DAG 的可组合对象的数据库。

item (id, info...)
link (parent_id, child_id)

出于陈旧的(不幸的是不可协商的)认证目的，他们现在希望为源和顶点的每个组合存储附加信息。例如作曲

  A
  |
  B
 / \
C   D

他们想要证书 (A,B) 证书 (A,C) 和证书 (A,D)。简单吧？

cert(parent_id, child_id, info...)

现在的问题是，这些证书应该针对每个路径，而不是每个节点。所以对于有共同祖先的元素

  A
 / \
B   C
 \ /
  D

我们需要证书 (A,B)、(A,C) 和 (A,D)[通过 B] 和 (A,D)[通过 C]

我想不出一种存储这些证书的方法，它不涉及存储对它所代表的路径中每个顶点的引用，但这似乎呈指数级增长。有数十万条记录，如果一些图表只包含几个共同的祖先，事情可能会很快失控。

除了为每个证书引用每个路径中的每个顶点之外，是否有更好的方法来存储这些路径？

Answer 1

如果需要存储它们，您肯定会拥有与路径一样多的记录。这里没办法。

如果我理解正确的话，您正在寻找一种设计来阻止您将所有顶点存储为单个属性(“A、B、D”)或单独的表。

在这种情况下，采用分层方法:

path_id  segment_id  next_vertex      -- which path it represents
1                    A
2                    B
3                    C
4                    D
5         1          B                 -- A B
6         1          C                 -- A C
7         2          D                 -- B D
8         3          D                 -- C D
9         5          D                 -- A B D
10        6          D                 -- A C D

这里的 segment_id 表示没有最后一个顶点的子路径。现在，例如，路径 10 表示“A->C->D”，它由“A->C”(路径 6)和最后添加的顶点 D 组成。您可以通过以相同的方式沿着树向下遍历层次结构。

请注意，我们在这里也得到了“退化路径”，它只包含一个顶点，其中 segment_id 为空。