[sf-perl] [sfpug] Practical theory: graphs

[chris mungall]

On Dec 15, 2005, at 11:15 AM, Chris Palmer wrote:

> Like Rich, I also did not get the original message. But here goes.
>
>> I'm looking for a practical, lay book on graph theory, especially one
>> that describes how to represent graphs in RDBMSs.
>
> I have *Introductory Graph Theory* by Gary Chartrand (published by
> Dover). It is approachable and application-oriented, but says nothing
> about RDBMSs.
>
> Why is it necessary to represent graphs in an RDBMS? I can't help but
> imagine that some graph-specific presistence mechanism would be simpler
> and more performant.

Representing graphs and trees in a RDBMS is vital for certain 
applications, for example molecular biology: species trees with 
evolutionary relationships and distances, graphs of interactions 
between genes, proteins and molecules in different cellular 
compartment. Having a normalised representation of the graph or tree 
modeled using the same formalism as the rest of your data allows you to 
do integrated queries using the same language (eg SQL). Modeling all 
your data using a graph formalism as opposed to relational is another 
option, but this can be difficult to scale.

Of course if your DBMS doesn't support recursive queries then you have 
to resort to either ugly imperative code or materializing the 
transitive closure of the graph (or representing your tree using a 
nested set model), or perhaps DBMS functions. There's well known 
techniques for each.

There is a good tutorial outlining some of these issues here:
http://www.people.virginia.edu/~wrp/papers/ismb02_sql.pdf

The examples are geared towards molecular biology, but should be 
broadly applicable. All the code is perl.

Kind of getting off topic for a perl list but if any locals have 
experience layering semantic web type metamodels (eg graph based 
formalisms such as RDF) over relational databases and getting decent 
performance, I'd be interested in chatting with you.

> -- 
> http://www.noncombatant.org/
> http://www.boshuda.com/
>
> _______________________________________________
> SanFrancisco-pm mailing list
> SanFrancisco-pm at pm.org
> http://mail.pm.org/mailman/listinfo/sanfrancisco-pm