On 10/13/05 8:27 AM, "Ivan Yu. Zolotukhin" <iz@xxxxxxxxxxx> wrote: > Hello, > > I'm trying to organize storage and processing of a graph (pretty spare, > 100,000 vertices and 5,000,000 edges) with PostgreSQL. > > I have two main problems: > - standart problem of finding all shortest paths between two given vertices; > - search thru vertices' properties with ordering by path lengths from > given vertix. > > So, basically, I need to decide what additional data (some preprocessed > data about a graph or indexes) I need to store, how to store it, and how > maintain it when graph changes. > > It seems that the second problem (ordering by path length) requires to > store all path lengths between all vertices pairs (roadmap), that is > very expensive to maintain. > > I would appreciate any suggestions... Try googling for "transitive closure SQL" for some hits on the subject. The following website describes how some folks have stored a DAG for a biological system: http://www.godatabase.org/dev/sql/doc/godb-sql-doc.html I don't know if any folks from the CHADO (http://www.gmod.org/schema/index.shtml) project can comment on computing the transitive closure using stored procedures, but I think they do that for their project. Sean ---------------------------(end of broadcast)--------------------------- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
