如何實現不涉及加載到內存的對象持久性？

Question

我有一個Graph對象（這是Perl），我計算它的transitive closure（即爲解決all-pairs shortest paths問題）。

從這個對象，我感興趣的計算：

1. 從任意點u最短路徑> - V
2. 所有頂點距離矩陣。
3. 一般可達性問題。
4. 一般圖形特徵（密度等）。

該圖有大約2000個頂點，因此計算傳遞閉包（使用Floyd-Warshall的算法）需要幾個小時。目前我只是緩存序列化對象（使用Storable，所以它已經非常高效）。

我的問題是，反序列化這個對象仍然需要相當長的時間（一分鐘左右），並消耗大約4GB的RAM。這是我的應用程序無法接受的。

因此，我一直在考慮如何設計一個數據庫模式來以'展開'的形式保存這個對象。換句話說，預先計算所有對最短路徑，並以適當的方式存儲這些路徑。然後，也許使用存儲過程來檢索必要的信息。

我的其他問題是，我沒有數據庫設計經驗，也沒有關於實現上述的線索，因此我的職位。我也想聽聽我可能無視的其他解決方案。謝謝！

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到length屬性。

但是，你可能需要一個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.