[sf-perl] [sfpug] Practical theory: graphs
cjm at fruitfly.org
Thu Dec 15 11:37:40 PST 2005
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:
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.
> SanFrancisco-pm mailing list
> SanFrancisco-pm at pm.org
More information about the SanFrancisco-pm