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

futuresandwich 发表于 Dev

期货三明治

客户端具有存储为简单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]

我想不出一种存储这些证书的方法，该方法不涉及在它所代表的路径中存储对每个顶点的引用，但这似乎令人恐惧。有成千上万的记录，如果一些图表仅包含一些共同的祖先，那么事情可能会很快失去控制。

是否有比仅针对每个证书引用每个路径中的每个顶点更好的方法来存储这些路径？

联合收割机

如果需要存储路径，那么您当然将拥有与路径一样多的记录。没办法

如果我理解正确，那么您将寻求一种设计，以防止您将所有顶点存储为单个属性（“ 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为null。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。