Re: Graph datatype addition

On Mon, Apr 29, 2013 at 10:50 AM, Merlin Moncure <mmoncure(at)gmail(dot)com> wrote:

> On Mon, Apr 29, 2013 at 9:25 AM, Atri Sharma <atri(dot)jiit(at)gmail(dot)com> wrote:
> >>
> >> 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).
> >
> > I completely agree. Initially, I was thinking of exposing the data to
> > user via HStore. But now, after Robert's suggestions, I think it will
> > be better to have an alternate representation. JSON seems to be an
> > excellent idea for that.
>
> I don't agree with this; JSON is not really designed to store graphs.
> You will probably need a customized internal representation, just like
> hstore, that expresses a graph like structure.
>
> This is not a trivial project.
>

Not trivial, indeed.

I see there being two directions where a data type goes.

1. We created JSON and XML types as ways of storing data that has a robust
validation system.

They're still, in a sense, just "plain old text", but it's "plain old text"
that the user can be certain satisfies the respective rules for
representations.

2. Some types support special operations to allow the data to be queried
in novel ways.

That's NOT the case, at this point, for JSON or XML.

But it certainly IS the case for Jeff Davis' "range types", which expose
access to some new sorts of data validation and indexing.

It is true for the inet type, which behaves rather differently from our
other types.

It is true for the tsearch indexes, that enable interesting random access
within some large "blobs" of stored data.

I'm not sure quite what we *would* want as the merits of graph-related
types.

I suspect that the best answer is NOT one where a graph is represented as a
value in a table; that has the implication that modifying The Graph
requires altering a single tuple, and that seems likely to become a
horrible bottleneck. I'm suspicious that using HSTORE leads down that
path, where you'll have a database that has a table with just one tuple in
it, and where it's nearly impossible to alter that tuple.

I'm having a hard time thinking about what it looks like to have a graph as
table except to effectively compose the graph as a set of nodes, one tuple
per node, and I'm not sure that a new data type has anything to contribute
to that.

The one place where I *could* see a special type having a contribution is
for there to be a data type that can contain an arbitrary number of links.
That means you have one tuple per node, and, instead of needing a tuple for
each link between nodes, you have one attribute indicating *all* the
links. (And "interesting" is for that one attribute to be usable for
foreign key purposes.) That has a hard time scaling in cases where nodes
are over-connected, which is, broadly speaking, an acceptable sort of
scenario.
--
When confronted by a difficult problem, solve it by reducing it to the
question, "How would the Lone Ranger handle this?"