Re: Graph datatype addition

On 30/04/13 12:33, Любен Каравелов wrote:
> ----- Цитат от Christopher Browne (cbbrowne(at)gmail(dot)com), на 29.04.2013 в 23:18 -----
>> 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.
>> ...
>
> Hello,
>
> From the start of the discussion I was trying to get what this graph
> data type should be... I could not grasp it.
>
> With the current postgres, in the most simple case we could do something
> like:
>
> create table node (
> node_id serial primary key,
> ...
> );
> create table edge(
> from integer references node,
> to integer[] -- each element references node
> );
>
> With the addition of foreign keys constraint on arrays elements (that I
> understand is work in progress), we could guarantee referential
> integrity of the graph - I really hope that it will be ready for 9.4.
>
> Without the array elements foreign keys constraints, if we have to
> guarantee the integrity we could do:
>
> create table edge(
> from integer referecens node,
> to integer references node,
> weight real,
> ...
> );
>
> What is missing are some algorithms. I have personaly implemented some
> algorithms using recursive queries and it is doable (most of my
> experience was with Oracle but lately I have put in production some
> postgresql schemas with recursive queries that are working just fine).
> For large scale eigen values factorisation (think pagerank) this
> sparse matrix form is reasonable data organisation (though I have
> doubts that the best place to run this job is in the database)
>
> Best regards
> luben
>
>
For directed graphs, where each node has a set of lines each with their
own weight, I would suggest:

create table node
(
id int primary key,
to_node_id integer[], -- references node(id)
weight float[], -- weight of line
...
);

So if nodeA has a line going to nodeB - then you can't go from nodeB
back to nodeA, unless nodeB has nodeA as a destination for one of its
lines. Would be best to ensure that the arrays have the same length!

This way lines can also have asymmetric weights.

Though it would be better to have something like:
create table node
(
id int primary key,
edges directed_line[],
...
);

Where using a 'directed_line' instance could be an object in its own
right - with functions to extract start/end nodes along with the weight
and to add/remove (destination_node, weight) pairs. Yet the system could
internally just store the start node once for an array of directed_lines
(though something other than array would be more appropriate).

Cheers,
Gavin