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

i have graph object (this in perl) compute transitive closure (i.e. solving all-pairs shortest paths problem).

from object, interested in computing:

1. shortest path vertices u -> v.
2. distance matrix vertices.
3. general reachability questions.
4. general graph features (density, etc).

the graph has 2000 vertices, computing transitive closure (using floyd-warshall's algorithm) takes couple hours. caching serialized object (using storable, it's pretty efficient already).

my problem is, deserializing object still takes fair amount of time (a minute or so), , consumes 4gb of ram. unacceptable application.

therefore i've been thinking how design database schema hold object in 'unfolded' form. in other words, precompute all-pairs shortest paths, , store in appropriate manner. then, perhaps use stored procedures retrieve necessary information.

my other problem is, have no experience database design, , have no clue implementing above, hence post. i'd hear other solutions may disregarding. thanks!

to start with, sounds need 2 entities: vertex , edge , perhaps couple tables results. suggest table stores node-to-node information. if reachable y relationship gets reachable attribute. here goes

vertex:     coordinates (x,y,...)     name: string     attributes of vertex*  association:      association_id: id     association_type: string  vertexinassociation:     vertex: (constrained vertex)     association: (constrained association)  associationattributes:     association_id: id (constrained association)     attribute_name: string     attribute_value: variable -- possibly string 

* might want store vertex attributes in table well, depending on how complex are.

the reason i'm adding complexity of association edge not felt directional , simplifies queries consider both vertexes members of set of vertexes "connected-by-edge-x"

thus edge association of edge type, have attribute of distance. path association of path type, , might have attribute of hops.

there might other more optimized schemas, 1 conceptually pure--even if doesn't make first-class concept of "edge" first class entity.

to create minimal edge need this:

begin transaction select associd = max(association_id) + 1 association insert association ( association_id, association_type )      values( associd, 'edge' ) insert      vertexinassociation( association_id, vertex_id )           select associd, ? -- $vertex->[0]->{id}     union select associd, ? -- $vertex->[1]->{id} insert associationattributes ( association_id, association_name, association_value )           select associd, 'length', 1      union select associd, 'distance', ? -- $edge->{distance}  commit 

you might want make association types classes of sorts. "edge" association automatically gets counted "reachable" association. otherwise, might want insert union select associd, reachable, 'true' in there well.

• and query union of reachable associations of both vertexes , dump them reachable associations other node if did not exist , dump existing length attribute value + 1 length attribute.

however, you'd want orm though, , manipulate inside perl.

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