Re: Graph datatype addition

On Mon, Apr 29, 2013 at 12:55 AM, Atri Sharma <atri.jiit@gmail.com> wrote:
>> It's probably pretty easy to add this, but I think the question is
>> what would make it better than storing the same representation in a
>> text field.
>
> I completely agree. The main point in making a new datatype would be
> to add support for operations that are normally done with graphs.
>
>
>>Obviously you get validation that the input is in the
>> correct format, but you could do that with a CHECK constraint, too, or
>> otherwise handle it in the application.  So I think the really
>> interesting question is: what operations would you support on this
>> data type?
>
> I can think of the standard tasks, i.e. searching if two nodes are
> connected or not,adding new nodes and edges, traversing the adjacency
> lists of nodes.
>
> If we add support for weighted graphs, we can probably add support for
> some common graph algorithms, such as Djikstra's algorithm, Bellman
> Ford algorithm, a MST making algorithm, network flow algorithms.
>
> The main idea is to allow user to work with graphs pretty easily, and
> allow the user to use the data present in his database to make graphs
> and then process them.
>
>> One of the problems you're likely to run into if you store the whole
>> graph as a single object is that it may make many of the things you
>> want to do with it not very efficient.
>
> Yes, I agree. On further thought, I believe it would be more of a pain
> if we stick to representing the whole thing as one.Rather,making
> multiple components will be more flexible and modular, and allow us to
> modify different components of the same graph without modifying or
> interfering with other components of the graph.
>
> I will think of a new design. I am still thinking of using HStore to
> store adjacency lists. This should have good performance for access of
> lists and similar tasks, IMO.

This is an interesting idea.  Historically I've always decomposed
graphs into relational structures because that's the only practical
way to query them.   Graphs are not currently able to be transported
out of the database currently via JSON so one of the areas to focus
your research will be how the client will consume the data.
libpqtypes is one way to do it, but that will really restrict you
audience so you'll probably need a rich set of functions present the
internal data (just like hstore).

Another area to focus research will be on searchability: how to use
GIST/GIN indexes to pull data out via an internal query string. An
overview of the current GIST based type implementations (like ltree)
couldn't hurt.

merlin