How do I implement object-persistence not involving loading to memory?

Question

I have a Graph object (this is in Perl) for which I compute its transitive closure (i.e. for solving the all-pairs shortest paths problem).

From this object, I am interested in computing:

1. Shortest path from any vertices u -> v.
2. Distance matrix for all vertices.
3. General reachability questions.
4. General graph features (density, etc).

The graph has about 2000 vertices, so computing the transitive closure (using Floyd-Warshall's algorithm) takes a couple hours. Currently I am simply caching the serialized object (using Storable, so it's pretty efficient already).

My problem is, deserializing this object still takes a fair amount of time (a minute or so), and consumes about 4GB of RAM. This is unacceptable for my application.

Therefore I've been thinking about how to design a database schema to hold this object in 'unfolded' form. In other words, precompute the all-pairs shortest paths, and store those in an appropriate manner. Then, perhaps use stored procedures to retrieve the necessary information.

My other problem is, I have no experience with database design, and have no clue about implementing the above, hence my post. I'd also like to hear about other solutions that I may be disregarding. Thanks!

Answer 1

To start with, sounds like you need two entities: vertex and edge and perhaps a couple tables for results. I would suggest a table that stores node-to-node information. If A is reachable from Y the relationship gets the reachable attribute. So here goes

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

* You might also want to store vertex attributes in a table as well, depending on how complex they are.

The reason that I'm adding the complexity of Association is that an edge is not felt to be directional and it simplifies queries to consider both vertexes to just be members of a set of vertexes "connected-by-edge-x"

Thus an edge is simply an association of edge type, which would have an attribute of distance. A path is an association of path type, and it might have an attribute of hops.

There might be other more optimized schemas, but this one is conceptually pure--even if it doesn't make the first-class concept of "edge" a first class entity.

To create an minimal edge you would need to do this:

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

You might also want to make association types classes of sorts. So that the "edge" association automatically gets counted as a "reachable" association. Otherwise, you might want to insert UNION select associd, reachable, 'true' in there as well.

• And then you could query a union of reachable associations of both vertexes and dump them as reachable associations to the other node if they did not exist and dump existing length attribute value + 1 into the length attribute.

However, you'd probably want an ORM for all that though, and just manipulate it inside the 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.