perl - 如何实现不涉及加载到内存的对象持久化？

Question

我有一个Graph对象(这是在 Perl 中)，我为其计算 transitive closure (即解决 all-pairs shortest paths 问题)。

从这个对象中，我对计算感兴趣:

1. 从任何顶点 u -> v 开始的最短路径。
2. 所有顶点的距离矩阵。
3. 一般可达性问题。
4. 一般图形特征(密度等)。

该图大约有 2000 个顶点，因此计算传递闭包(使用 Floyd-Warshall 的算法)需要几个小时。目前我只是缓存序列化对象(使用 Storable ，所以它已经非常高效)。

我的问题是，反序列化这个对象仍然需要相当长的时间(一分钟左右)，并且消耗大约 4GB 的 RAM。这对我的申请来说是 Not Acceptable 。

因此，我一直在考虑如何设计一个数据库模式来以“展开”的形式保存这个对象。换句话说，预先计算所有对的最短路径，并以适当的方式存储它们。然后，也许使用存储过程来检索必要的信息。

我的另一个问题是，我没有数据库设计经验，并且不知道如何实现上述内容，因此我发表了这篇文章。我还想听听我可能忽略的其他解决方案。谢谢!

Answer 1

首先，听起来您需要两个实体:顶点和边，也许还有几个结果表。我建议使用一个存储节点到节点信息的表。如果 A 从 Y 可达，则关系获得可达属性。所以这里是

Vertex:
    any coordinates (x,y,...)
    name: string
    any attributes of a vertex*

Association: 
    association_id: ID
    association_type: string

VertexInAssociation:
    vertex: (constrained to Vertex)
    association: (constrained to association)

AssociationAttributes:
    association_id: ID (constrained to association)
    attribute_name: string
    attribute_value: variable -- possibly string

* 您可能还想将顶点属性存储在表中，具体取决于它们的复杂程度。

我添加关联复杂性的原因是，边缘不被认为是有方向的，并且它简化了查询以将两个顶点视为只是一组顶点“connected-by-edge-x”的成员

因此，边只是边类型的关联，它具有距离属性。路径是路径类型的关联，并且它可能具有跳数属性。

可能还有其他更优化的模式，但这个模式在概念上是纯粹的——即使它没有使“边缘”的第一类概念成为第一类实体。

要创建最小边缘，您需要执行以下操作:

begin transaction
select associd = max(association_id) + 1 from Association
insert into Association ( association_id, association_type ) 
    values( associd, 'edge' )
insert 
    into VertexInAssociation( association_id, vertex_id )
          select associd, ? -- $vertex->[0]->{id}
    UNION select associd, ? -- $vertex->[1]->{id}
insert into AssociationAttributes ( association_id, association_name, association_value )
          select associd, 'length', 1 
    UNION select associd, 'distance', ? -- $edge->{distance}

commit

您可能还想将关联类型分类。这样“边缘”关联就会自动被算作“可达”关联。否则，您可能还想在其中插入 UNION select associd,reachable, 'true' 。

• 然后，您可以查询两个顶点的可达关联的并集，如果它们不存在，则将它们作为可达关联转储到另一个节点，并将现有长度属性值 + 1 转储到长度属性中。

但是，您可能需要一个 ORM 来完成这一切，并且只需在 Perl 内操作它即可。

my $v1 = Vertex->new( 'V', x => 23, y => 89, red => 'hike!' );
my $e  = Edge->new( $v1, $v2 ); # perhaps Edge knows how to calculate distance.