[sf-perl] Practical theory: graphs

Quinn Weaver qw at sf.pm.org
Fri Dec 16 20:56:02 PST 2005


Oops, this discussion got forked into two threads, one on the SF Perl
Users' Group list, one on the SF PostgreSQL Users' Group list.  (This
was due to the unfortunate similarity of names, which caused an early
poster to reply to the wrong SFPUG.)

This post attempts to merge the theads by responding to everyone at
once ;) It is cross-posted to both lists.  I've also attached the full
threads as a text file, for those interested in the gory details.

                        *       *       *

At the very end of the thread, Elein <elein at varlena.com> made the
ridiculous request that I actually explain what I am trying to
represent. ;) It's not exactly a secret, so here goes:

I am representing a hierarchy of menus in a phone menu system, like
the one you get when calling your bank or ISP.  Such systems are
called IVRs (for Integrated Voice Response).

This is for version 2 of a product called Dido.  I'm debuting version
1 in a talk at the O'Reilly Emerging Telephony Conference.  Dido is a
programmer-friendly system for building IVRs.  It is built on top of the
open-source PBX Asterisk.

One of Dido's novel features is that it can reorder menu items
according to popularity.  So, for instance, if 80% of users are
choosing option 3 in submenu 2 of menu 4, Dido can automatically copy
that option into the main menu, making callers' lives easier.

Another novel feature is that you get a Perl API for programming
"dynamic content".  Actually it's XML with embedded Perl, very similar
to the Web template model of programming.  I'd like to gush on about
it, but I'm publishing an article on O'Reilly's Web site at some point.
When it's up, I'll just post the URL.

Before you ask, I do plan to give my O'Reilly talk to San Francisco
Perl Mongers.

Anyway...

The system of nested menus is essentially a graph.  Menus are nodes
with children (which may themselves be menus).  An end node represents
the place where you actually get the person (or automated system) that
you wanted.

In version 1, Dido concerns itself only with the end nodes reached by
users (or by an individual user identified by Caller*ID).  It logs
this information in a database (SQLite--sorry, but I didn't want to
force a full PostgreSQL installation.  Maybe Version 2 will include an
option to use PG.)  Periodically Dido reads the DB to see which end
nodes are most popular, and moves them up.

This makes sense, as what you usually care about it where you end
up, not how you got there.  However, you can conceive of a scenario
where you want to reduce the number of hops needed to reach an end
node, without actually changing the order of menus.  Maybe.  I'm
still playing around with the idea.

To do this, you need a log of how each users traverses the graph.
This seems to suggest a more full-featured representation of the graph
in the database.  That is, I had expected to use an RDBMs for
this.

However, some posters have suggested that this is not the best way to
represent graphs, and that i should try a graph-specific storage
medium rather than a relational one.  Chris Palmer was the first to
say this directly.  Before that, Rich Morin hinted at it, and noted
performance problems with representing large graphs.

Chris Mungall made a similar observation about performance, based on
experience with molecular biology systems.  However, he also said that
the performance of graph-based systems a problem!  Maybe this is just
an intrinsic problem to the data structure?

In fact, Chris Mungall <cjm at fruitfly.org> wrote this plea:

> 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.

Myself, I'm not worried about performance.  My graphs are quite
small.  (Phone menu systems aren't that big, although they sometimes
seem that way to the beleagured user. ;) )

Then Josh Berkus chimed in:

> As much as I'm an RDBMS geek, I'll have to admit that there's no easy way 
> to do graphs in SQL.   The one really big implementation I know of is 
> using a separate graph engine as a pseudotable and plugging that in to 
> their RDBMS.   The problem with that approach, of course, is that it's not 
> transaction-compliant.

Ouch!  So maybe an RDBMS is not the best bet for me.  What kind
of graph-specific representation systems are there?  Can people
recommend any?

Speaking of graph systems versus RDBMS systems, Rich Morin
<rdm at cfcl.com> suggested object-role modeling as a third, orthogonal
approach.  I don't really grok it, but apparently it's a way to
generalize specific statements about relationships of things in the
world, which can lead you to develop a data model for them.

I'm pretty sure I don't need this, because the basic "shape" of
a menu system is well-understood and invariant.  Is that right, or
am I missing the point?

Assuiming I do use a graphy, another question was, what kind of graphs
are we talking about, anyway?  David Fetter pointed out that the tree
is the most used kind of graph in RDBMS-land.  This was helpful, since
I didn't know that.

In version 1, menu systems are always trees, for simplicity's sake.

However, it is conceivable to allow cycles (e.g. option 3 in menu 2
returns you to option 5 in the main menu, or to some other "sibling"
menu elsewhere in the hierarchy).  I don't know how much harder this
would make my code.  This is one of the major things I wanted to find
out.

David also warned me that I will be stuck with mathematical theory to
some extent, because there are important issues like NP hardness that
you need to know about.  I am OK with stuff like this; I in fact, it's
what I want.  I want to know general properties of different kinds of
graphs.  I just don't want to see the proofs or formal statements that
lead to them.  (To give you an idea, a while ago I read an academic
article on Bayesian networks.  I got about halfway through before I
even understood how they worked, at which point I realized they were
useless for what I was doing.  [I'd gotten a bad recommendation from a
statistician.]  _This_ is what I want to avoid.)

So texts are important.  Chris Palmer recommend _Introductory Graph
Theory_, by Gary Chartrand.  It sounds as if it deals with graph theory
at the level I want, but doesn't deal with RDBMSs at all.  This actually
sounds like a good bet, for starters.

Other books look less promising.  Josh Berkus again:

> Hmmmm ... does Celko's tree book cover graphs?   DF?

And David Fetter responding:

> Not really.

> IMHO, the tree book is a rehash of his other stuff on trees in SQL for
> Smarties, 3rd. Ed.

But Elein's article looks quite promising:

> I have an article with some algorithms for setting up a tree graph
> and traversing it, deleting nodes, etc.
>
> http://www.varlena.com/GeneralBits/65.php

That's assuming I use a tree in an RDBMS, not a cyclical graph
or a non-RDBMS-based system.

Questions, questions!  Why do I get the feeling that I'm suffering from
Second System Syndrome? ;)

Thanks, everybody, for all your suggestions and insights, and for
putting up with the long post.  I hope there's more good stuff to
come. :)

--
qw (Quinn Weaver); #President, San Francisco Perl Mongers
=for information, visit http://sf.pm.org/weblog =cut
-------------- next part --------------
>From sfpug-owner+M1387 at postgresql.org Thu Dec 15 01:44:13 2005
Return-Path: <sfpug-owner+M1387 at postgresql.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBF9iDVO029995
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 01:44:13 -0800
Received: (qmail 16314 invoked by alias); 15 Dec 2005 09:44:13 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 5745 invoked from network); 15 Dec 2005 09:44:13 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 09:44:13 -0000
Received: from mx1.hub.org (mx1.hub.org [200.46.208.251])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBF9nNeg052304
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 01:49:24 -0800 (PST)
	(envelope-from sfpug-owner+M1387 at postgresql.org)
Received: from postgresql.org (postgresql.org [200.46.204.71])
	by mx1.hub.org (Postfix) with ESMTP id 1D920652F2C;
	Thu, 15 Dec 2005 05:44:11 -0400 (AST)
X-Original-To: sfpug-postgresql.org at localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id 2129D9DCAB2
	for <sfpug-postgresql.org at localhost.postgresql.org>; Thu, 15 Dec 2005 05:44:06 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
 by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
 with ESMTP id 50666-08 for <sfpug-postgresql.org at localhost.postgresql.org>;
 Thu, 15 Dec 2005 05:44:06 -0400 (AST)
X-Greylist: delayed 03:01:28.562777 by SQLgrey-
Received: from svr2.postgresql.org (svr2.postgresql.org [65.19.161.25])
	by postgresql.org (Postfix) with ESMTP id 0A8029DCB5E
	for <sfpug at postgresql.org>; Thu, 15 Dec 2005 05:44:02 -0400 (AST)
Received: from cfcl.com (cpe-24-221-172-174.ca.sprintbbd.net [24.221.172.174])
	by svr2.postgresql.org (Postfix) with ESMTP id A2C7BF0B1C
	for <sfpug at postgresql.org>; Thu, 15 Dec 2005 06:42:33 +0000 (GMT)
Received: from cfcl.com (localhost.cfcl.com [127.0.0.1])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBF6leeg092030
	for <sfpug at postgresql.org>; Wed, 14 Dec 2005 22:47:40 -0800 (PST)
	(envelope-from qweaver at cfcl.com)
Received: (from qweaver at localhost)
	by cfcl.com (8.12.6/8.12.6/Submit) id jBF6lev4092029
	for sfpug at postgresql.org; Wed, 14 Dec 2005 22:47:40 -0800 (PST)
Date: Wed, 14 Dec 2005 22:47:40 -0800
From: Quinn Weaver <qw at sf.pm.org>
To: SF Postgres <sfpug at postgresql.org>
Subject: [sfpug] Practical theory:  graphs
Message-ID: <20051215064740.GD63981 at cfcl.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.4i
X-Virus-Scanned: by amavisd-new at hub.org
X-Mailing-List: sfpug
List-Archive: <http://archives.postgresql.org/sfpug>
List-Help: <mailto:majordomo at postgresql.org?body=help>
List-ID: <sfpug.postgresql.org>
List-Owner: <mailto:sfpug-owner at postgresql.org>
List-Post: <mailto:sfpug at postgresql.org>
List-Subscribe: <mailto:majordomo at postgresql.org?body=sub%20sfpug>
List-Unsubscribe: <mailto:majordomo at postgresql.org?body=unsub%20sfpug>
Precedence: bulk
Sender: sfpug-owner at postgresql.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 715
Lines: 21

Hi, all,

I'm looking for a practical, lay book on graph theory, especially one
that describes how to represent graphs in RDBMSs.

I fear I am stuck with something by Date, but... Do people have any
other recommendations?

I specifically don't want formal proofs of mathematical properties of
graphs.  What I want is something more emic: What can you represent
with x kind of graph?  What are its properties?  What are the
algorithms for traversing (or otherwise processing it)?  In short,
what is it good for?

If anyone can come up with this, I owe them a huge debt of gratitude. :)

Best regards,

--
qw (Quinn Weaver); #President, San Francisco Perl Mongers
=for information, visit http://sf.pm.org/weblog =cut

>From sanfrancisco-pm-bounces at pm.org Thu Dec 15 06:01:02 2005
Return-Path: <sanfrancisco-pm-bounces at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFE12dv001047
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 06:01:02 -0800
Received: (qmail 27729 invoked by alias); 15 Dec 2005 14:01:02 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 13393 invoked from network); 15 Dec 2005 14:01:02 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 14:01:02 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFE6Ceg043477
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 06:06:12 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP
	id 465541777B; Thu, 15 Dec 2005 06:00:59 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 32666 invoked from network); 15 Dec 2005 14:00:51 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 14:00:51 -0000
Received: (qmail 27786 invoked by uid 225); 15 Dec 2005 14:00:51 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 27782 invoked by alias); 15 Dec 2005 14:00:50 -0000
Received-SPF: neutral (x1.develooper.com: local policy)
Received: from cpe-24-221-172-174.ca.sprintbbd.net (HELO cfcl.com)
	(24.221.172.174) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 06:00:33 -0800
Received: from fetter.org (dsl092-188-065.sfo1.dsl.speakeasy.net
	[66.92.188.65])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFE5deg043348
	for <sfpug at sf.pm.org>; Thu, 15 Dec 2005 06:05:40 -0800 (PST)
	(envelope-from shackle at fetter.org)
Received: from fetter.org (localhost.localdomain [127.0.0.1])
	by fetter.org (8.13.4/8.12.10) with ESMTP id jBFE0QdE028659
	for <sfpug at sf.pm.org>; Thu, 15 Dec 2005 06:00:27 -0800
Received: (from shackle at localhost)
	by fetter.org (8.13.4/8.13.4/Submit) id jBFE0QIx028658
	for sfpug at sf.pm.org; Thu, 15 Dec 2005 06:00:26 -0800
Date: Thu, 15 Dec 2005 06:00:26 -0800
From: David Fetter <david at fetter.org>
To: "San Francisco Perl Users' Group" <sfpug at sf.pm.org>
Message-ID: <20051215140026.GA19716 at fetter.org>
References: <20051215064740.GD63981 at cfcl.com>
Mime-Version: 1.0
Content-Disposition: inline
In-Reply-To: <20051215064740.GD63981 at cfcl.com>
User-Agent: Mutt/1.4.2.1i
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces at pm.org
Errors-To: sanfrancisco-pm-bounces at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 1669
Lines: 50

On Wed, Dec 14, 2005 at 10:47:40PM -0800, Quinn Weaver wrote:
> Hi, all,
> 
> I'm looking for a practical, lay book on graph theory, especially
> one that describes how to represent graphs in RDBMSs.
> 
> I fear I am stuck with something by Date, but... Do people have any
> other recommendations?

Sure :)

First, a few refs on graph theory in general:
http://en.wikipedia.org/wiki/Graph_theory
The references there include a book from Springer in PDF form :)

The problem of is one representing graphs in RDBMSs is at the outer
edge of theory right now, so you'll be doing some pretty serious
coding to make it happen.  The kind of graph where the most has
already happened as far as RDBMSs go is a tree.

http://www.grzm.com/fornow/archives/2004/07/10/static_hierarchies
http://www.mrnaz.com/static/articles/trees_in_sql_tutorial/
http://www.sai.msu.su/~megera/postgres/gist/ltree/

> I specifically don't want formal proofs of mathematical properties
> of graphs.  What I want is something more emic: What can you
> represent with x kind of graph?  What are its properties?  What are
> the algorithms for traversing (or otherwise processing it)?  In
> short, what is it good for?

A lot of the general questions about graphs are essentially
mathematical in nature and end up with phrases like "NP-hard" or
"NP-complete."

> If anyone can come up with this, I owe them a huge debt of
> gratitude. :)

HTH :)

Cheers,
D
-- 
David Fetter david at fetter.org http://fetter.org/
phone: +1 415 235 3778

Remember to vote!
_______________________________________________
SanFrancisco-pm mailing list
SanFrancisco-pm at pm.org
http://mail.pm.org/mailman/listinfo/sanfrancisco-pm

>From sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org Thu Dec 15 08:57:50 2005
Return-Path: <sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFGvoRt003766
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 08:57:50 -0800
Received: (qmail 23218 invoked by alias); 15 Dec 2005 16:56:42 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 203 invoked from network); 15 Dec 2005 16:56:41 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 16:56:41 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFH1reg007819
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 09:01:53 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP id 4E3A3177AF
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 08:56:36 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 29036 invoked from network); 15 Dec 2005 16:56:29 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 16:56:29 -0000
Received: (qmail 31215 invoked by uid 225); 15 Dec 2005 16:56:28 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 31208 invoked by alias); 15 Dec 2005 16:56:28 -0000
Received-SPF: pass (x1.develooper.com: local policy)
Received: from cpe-24-221-172-174.ca.sprintbbd.net (HELO cfcl.com)
	(24.221.172.174) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 08:56:19 -0800
Received: from [192.168.254.205] ([192.168.254.205])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFH1Oeh007489
	for <sanfrancisco-pm at pm.org>; Thu, 15 Dec 2005 09:01:25 -0800 (PST)
	(envelope-from rdm at cfcl.com)
Mime-Version: 1.0
Message-Id: <p06230984bfc738e705d2@[192.168.254.205]>
In-Reply-To: <20051215140026.GA19716 at fetter.org>
References: <20051215064740.GD63981 at cfcl.com>
	<20051215140026.GA19716 at fetter.org>
Date: Thu, 15 Dec 2005 08:56:08 -0800
To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
From: Rich Morin <rdm at cfcl.com>
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org
Errors-To: sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 4997
Lines: 123

[Somehow, I missed the original message, so I'm working from DF's response.
 Hope I didn't miss anything crucial.  -r]


QW> I'm looking for a practical, lay book on graph theory, especially
QW> one that describes how to represent graphs in RDBMSs.
QW> ...
QW> I specifically don't want formal proofs of mathematical properties
QW> of graphs.  What I want is something more emic: What can you
QW> represent with x kind of graph?  What are its properties?  What are
QW> the algorithms for traversing (or otherwise processing it)?  In
QW> short, what is it good for?

Before I get into the real question, was "emic" a typo or are you using
Pike's neologism in some arcane manner?

>As Pike defines it, the emic perspective focuses on the intrinsic cultural
>distinctions that are meaningful to the members of a given society (e.g.,
>whether the natural world is distinguished from the supernatural realm in
>the worldview of the culture) in the same way that phonemic analysis
>focuses on the intrinsic phonological distinctions that are meaningful to
>speakers of a given language (e.g., whether the phones /b/ and /v/ make a
>contrast in meaning in a minimal pair in the language).  The native
>members of a culture are the sole judges of the validity of an emic
>description, just as the native speakers of a language are the sole judges
>of the accuracy of a phonemic identification.

http://faculty.ircc.cc.fl.us/faculty/jlett/Article%20on%20Emics%20and%20Etics.htm


I've been looking into graph representations for a while, concentrating on
the use of graphs to represent concepts, metadata, etc.  As you may know,
there are all sorts of graph-based representations for this sort of thing,
including Conceptual Graphs, RDF, Topic Maps, ...  The variations are both
structural and semantic, but assorted efforts are being made at solving the
interchange problem, etc.


At the risk of being yelled at by DF, I'll note that an easy and flexible
way to store a graph in a DBMS is as an edge list, stored in a single table:

  source  |  target  |  edge_type

This technique is used by RDF, the Protege folks
(http://protege.stanford.edu),
etc.  Aside from flexibility (adding new structure is REAL easy), it has the
advantage that all edges are bi-directional.  Finally, it's fairly fast to
get
answers to questions such as "find all of the nodes that are connected by an
edge of type E".  In some other representations, this would require walking
the
entire graph!

However, it is not without problems.  As DF would point out, it discards
many
of the benefits of the RDBMS, making the application responsible for
ensuring
consistency, etc.  Also, the apparent simplicity of each edge must be
balanced
against the number of edges that are needed to do anything useful.  Finally,
scaling (e.g., performance on large graphs) can be a real issue.


I've recently become quite interested in Object-Role Modeling (ORM), which
offers a way to map conceptual descriptions into RDBMS tables.  It looks
like
it combines nice semantics with industrial-strength DBMS design.

Basically, the ORM approach starts with "examples", such as:

  Quinn travels by bicycle.
  David travels by car.

It then formalizes these into "facts", adding entity type information, etc.

  The Person named "Quinn" Travels_by Vehicle "bicycle".
  The Person named "David" Travels_by Vehicle "car".

These facts are used to define "instance diagrams", which are generalized
into
"conceptual schema diagrams".  These diagrams have nodes for entities (e.g.,
Person, Vehicle) and N-ary relationships:

  "... travels_by ..."
  "... traveled_by ... to ... on ..."

Relationship nodes are subdivided into "roles", allowing the diagram to show
which entity plays which role(s) in each relationship.

After assorted constraints (etc) have been added, the diagram can be turned
into a set of table definitions.  Each relationship turns into a table; each
role turns into a column:

  Travels_by:   Person   Vehicle
                ------   -------
                Quinn    bicycle
                David    car

The definitive book on the subject is

  Information Modeling and Relational Databases:
  From Conceptual Analysis to Logical Design

  Terry Halpin
  Morgan Kaufmann, ISBN 1-55860-672-6

Terry Halpin also maintains a web site at http://www.orm.net.  Although no
Open Source tools currently exist for ORM, this is in the process of being
addressed.  Let me know if you want more details...

-r

P.S.  Note that "ORM" is a dangerously overloaded acronym.  A Google search
      for ORM will bring up all sorts of information on Operational Risk
      Management, Object-Relational Mapping, etc!
-- 
email: rdm at cfcl.com; phone: +1 650-873-7841
http://www.cfcl.com        - Canta Forda Computer Laboratory
http://www.cfcl.com/Meta   - The FreeBSD Browser, Meta Project, etc.
_______________________________________________
SanFrancisco-pm mailing list
SanFrancisco-pm at pm.org
http://mail.pm.org/mailman/listinfo/sanfrancisco-pm

>From sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org Thu Dec 15 11:17:42 2005
Return-Path: <sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFJHgEa006271
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 11:17:42 -0800
Received: (qmail 10087 invoked by alias); 15 Dec 2005 19:17:41 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 4160 invoked from network); 15 Dec 2005 19:17:41 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 19:17:41 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJMreg062825
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 11:22:53 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP id 7AA72177BD
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 11:17:38 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 9633 invoked from network); 15 Dec 2005 19:17:31 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 19:17:31 -0000
Received: (qmail 17098 invoked by uid 225); 15 Dec 2005 19:17:30 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 17093 invoked by alias); 15 Dec 2005 19:17:30 -0000
Received-SPF: pass (x1.develooper.com: local policy)
Received: from 69-12-134-80.dsl.static.sonic.net (HELO alan.noncombatant.org)
	(69.12.134.80) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 11:17:22 -0800
Received: by alan.noncombatant.org (Postfix, from userid 1000)
	id 4309A49F9B; Thu, 15 Dec 2005 11:15:43 -0800 (PST)
Date: Thu, 15 Dec 2005 11:15:43 -0800
From: Chris Palmer <chris at noncombatant.org>
To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
Message-ID: <20051215191543.GA32539 at nodewarrior.org>
References: <20051215064740.GD63981 at cfcl.com>
	<20051215140026.GA19716 at fetter.org>
Mime-Version: 1.0
Content-Disposition: inline
In-Reply-To: <20051215140026.GA19716 at fetter.org>
User-Agent: Mutt/1.5.9i
Cc: "San Francisco Perl Users' Group" <sfpug at sf.pm.org>
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org
Errors-To: sanfrancisco-pm-bounces+qw=sf.pm.org at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 720
Lines: 22

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.


-- 
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

>From sanfrancisco-pm-bounces at pm.org Thu Dec 15 11:17:50 2005
Return-Path: <sanfrancisco-pm-bounces at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFJHom7006287
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 11:17:50 -0800
Received: (qmail 11192 invoked by alias); 15 Dec 2005 19:17:50 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 13974 invoked from network); 15 Dec 2005 19:17:49 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 19:17:49 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJN0eg062905
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 11:23:01 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP
	id E2703177D4; Thu, 15 Dec 2005 11:17:45 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 9690 invoked from network); 15 Dec 2005 19:17:39 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 19:17:39 -0000
Received: (qmail 17155 invoked by uid 225); 15 Dec 2005 19:17:38 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 17148 invoked by alias); 15 Dec 2005 19:17:38 -0000
Received-SPF: neutral (x1.develooper.com: local policy)
Received: from cpe-24-221-172-174.ca.sprintbbd.net (HELO cfcl.com)
	(24.221.172.174) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 11:17:30 -0800
Received: from alan.noncombatant.org (69-12-134-80.dsl.static.sonic.net
	[69.12.134.80])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJMXeg062553
	for <sfpug at sf.pm.org>; Thu, 15 Dec 2005 11:22:38 -0800 (PST)
	(envelope-from chris at noncombatant.org)
Received: by alan.noncombatant.org (Postfix, from userid 1000)
	id 4309A49F9B; Thu, 15 Dec 2005 11:15:43 -0800 (PST)
Date: Thu, 15 Dec 2005 11:15:43 -0800
From: Chris Palmer <chris at noncombatant.org>
To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
Message-ID: <20051215191543.GA32539 at nodewarrior.org>
References: <20051215064740.GD63981 at cfcl.com>
	<20051215140026.GA19716 at fetter.org>
Mime-Version: 1.0
Content-Disposition: inline
In-Reply-To: <20051215140026.GA19716 at fetter.org>
User-Agent: Mutt/1.5.9i
Cc: "San Francisco Perl Users' Group" <sfpug at sf.pm.org>
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces at pm.org
Errors-To: sanfrancisco-pm-bounces at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 720
Lines: 22

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.


-- 
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

>From sanfrancisco-pm-bounces at pm.org Thu Dec 15 11:27:03 2005
Return-Path: <sanfrancisco-pm-bounces at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFJR3Uh006447
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 11:27:03 -0800
Received: (qmail 13237 invoked by alias); 15 Dec 2005 19:27:02 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 27832 invoked from network); 15 Dec 2005 19:27:00 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 19:27:00 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJWAeg068619
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 11:32:12 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP
	id 306D017789; Thu, 15 Dec 2005 11:26:56 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 10794 invoked from network); 15 Dec 2005 19:26:52 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 19:26:52 -0000
Received: (qmail 20418 invoked by uid 225); 15 Dec 2005 19:26:52 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 20409 invoked by alias); 15 Dec 2005 19:26:51 -0000
Received-SPF: pass (x1.develooper.com: local policy)
Received: from dsl092-188-065.sfo1.dsl.speakeasy.net (HELO fetter.org)
	(66.92.188.65) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 11:26:43 -0800
Received: from fetter.org (localhost.localdomain [127.0.0.1])
	by fetter.org (8.13.4/8.12.10) with ESMTP id jBFJQd96008137;
	Thu, 15 Dec 2005 11:26:39 -0800
Received: (from shackle at localhost)
	by fetter.org (8.13.4/8.13.4/Submit) id jBFJQdeq008136;
	Thu, 15 Dec 2005 11:26:39 -0800
Date: Thu, 15 Dec 2005 11:26:39 -0800
From: David Fetter <david at fetter.org>
To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
Message-ID: <20051215192638.GA8072 at fetter.org>
References: <20051215064740.GD63981 at cfcl.com>
	<20051215140026.GA19716 at fetter.org>
	<20051215191543.GA32539 at nodewarrior.org>
Mime-Version: 1.0
Content-Disposition: inline
In-Reply-To: <20051215191543.GA32539 at nodewarrior.org>
User-Agent: Mutt/1.4.2.1i
Cc: "San Francisco Perl Users' Group" <sfpug at sf.pm.org>
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces at pm.org
Errors-To: sanfrancisco-pm-bounces at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 1227
Lines: 32

On Thu, Dec 15, 2005 at 11:15:43AM -0800, 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.

I'm sure Quinn can answer this authoritatively, but I have a few
ideas.  For example, the "nodes" and "edges" might also be other kinds
of objects that fit in an RDBMS better than general graphs do, and
they might need other properties than whatever a graph-specific
storage mechanism would have.  Telephone numbers in a telco's billing
system would be an example of this.

Cheers,
D
-- 
David Fetter david at fetter.org http://fetter.org/
phone: +1 415 235 3778

Remember to vote!
_______________________________________________
SanFrancisco-pm mailing list
SanFrancisco-pm at pm.org
http://mail.pm.org/mailman/listinfo/sanfrancisco-pm

>From sanfrancisco-pm-bounces at pm.org Thu Dec 15 11:24:25 2005
Return-Path: <sanfrancisco-pm-bounces at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFJOPAj006409
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 11:24:25 -0800
Received: (qmail 3369 invoked by alias); 15 Dec 2005 19:24:25 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 15721 invoked from network); 15 Dec 2005 19:24:23 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 19:24:23 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJTPeg066382
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 11:29:25 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP
	id 1D1191778C; Thu, 15 Dec 2005 11:24:10 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 10510 invoked from network); 15 Dec 2005 19:24:07 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 19:24:07 -0000
Received: (qmail 19549 invoked by uid 225); 15 Dec 2005 19:24:07 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 19541 invoked by alias); 15 Dec 2005 19:24:06 -0000
Received-SPF: pass (x1.develooper.com: local policy)
Received: from server227.ethosmedia.com (HELO davinci.ethosmedia.com)
	(209.128.84.227) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 11:23:58 -0800
X-EthosMedia-Virus-Scanned: no infections found
Received: from [64.81.245.111] (account josh at agliodbs.com HELO [192.168.1.27])
	by davinci.ethosmedia.com (CommuniGate Pro SMTP 4.1.8)
	with ESMTP id 8695322; Thu, 15 Dec 2005 11:26:33 -0800
From: Josh Berkus <josh at agliodbs.com>
Organization: Aglio Database Solutions
To: sanfrancisco-pm at pm.org
Date: Thu, 15 Dec 2005 11:28:57 -0800
User-Agent: KMail/1.8
References: <20051215064740.GD63981 at cfcl.com>
	<20051215140026.GA19716 at fetter.org>
	<20051215191543.GA32539 at nodewarrior.org>
In-Reply-To: <20051215191543.GA32539 at nodewarrior.org>
MIME-Version: 1.0
Content-Disposition: inline
Message-Id: <200512151128.58224.josh at agliodbs.com>
Cc: "San Francisco Perl Users' Group" <sfpug at sf.pm.org>
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: josh at agliodbs.com,
        San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces at pm.org
Errors-To: sanfrancisco-pm-bounces at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 835
Lines: 22

Chris,

> 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.

As much as I'm an RDBMS geek, I'll have to admit that there's no easy way 
to do graphs in SQL.   The one really big implementation I know of is 
using a separate graph engine as a pseudotable and plugging that in to 
their RDBMS.   The problem with that approach, of course, is that it's not 
transaction-compliant.

-- 
__Aglio Database Solutions_______________
Josh Berkus		       Consultant
josh at agliodbs.com	 www.agliodbs.com
Ph: 415-752-2500	Fax: 415-752-2387
2166 Hayes Suite 200	San Francisco, CA
_______________________________________________
SanFrancisco-pm mailing list
SanFrancisco-pm at pm.org
http://mail.pm.org/mailman/listinfo/sanfrancisco-pm

>From sanfrancisco-pm-bounces at pm.org Thu Dec 15 11:38:23 2005
Return-Path: <sanfrancisco-pm-bounces at pm.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFJcNr8006636
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 11:38:23 -0800
Received: (qmail 23313 invoked by alias); 15 Dec 2005 19:38:23 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 31052 invoked from network); 15 Dec 2005 19:38:22 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 19:38:22 -0000
Received: from x6.develooper.com (x6.develooper.com [63.251.223.186])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJhYeg073388
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 11:43:34 -0800 (PST)
	(envelope-from sanfrancisco-pm-bounces at pm.org)
Received: from x6.develooper.com (localhost.localdomain [127.0.0.1])
	by x6.develooper.com (Postfix) with ESMTP
	id DC3E7177D7; Thu, 15 Dec 2005 11:38:19 -0800 (PST)
Delivered-To: mailman-sanfrancisco-pm at mailman.pm.dev
Received: (qmail 14351 invoked from network); 15 Dec 2005 19:38:08 -0000
Received: from x1a.develooper.com (HELO x1.develooper.com) (216.52.237.111)
	by lists.develooper.com with SMTP; 15 Dec 2005 19:38:08 -0000
Received: (qmail 24489 invoked by uid 225); 15 Dec 2005 19:38:08 -0000
Delivered-To: sanfrancisco-pm at pm.org
Received: (qmail 24484 invoked by alias); 15 Dec 2005 19:38:07 -0000
Received-SPF: neutral (x1.develooper.com: local policy)
Received: from cpe-24-221-172-174.ca.sprintbbd.net (HELO cfcl.com)
	(24.221.172.174) by la.mx.develooper.com (qpsmtpd/0.28) with ESMTP;
	Thu, 15 Dec 2005 11:37:46 -0800
Received: from mail.fruitfly.org (ci.lbl.gov [131.243.192.220])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFJgteg073158
	for <sfpug at sf.pm.org>; Thu, 15 Dec 2005 11:42:56 -0800 (PST)
	(envelope-from cjm at fruitfly.org)
Received: from localhost (localhost [127.0.0.1])
	by mail.fruitfly.org (Postfix on SuSE Linux eMail Server 3.0) with
	ESMTP id 3927C24D0B7; Thu, 15 Dec 2005 12:33:12 -0800 (PST)
Received: from mail.fruitfly.org ([127.0.0.1])
	by localhost (mail.fruitfly.org [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id 09585-04; Thu, 15 Dec 2005 12:33:11 -0800 (PST)
Received: from [131.243.195.208] (skerryvore.dhcp.lbl.gov [131.243.195.208])
	by mail.fruitfly.org (Postfix on SuSE Linux eMail Server 3.0) with
	ESMTP id E3AE8247F7B; Thu, 15 Dec 2005 12:33:10 -0800 (PST)
In-Reply-To: <20051215191543.GA32539 at nodewarrior.org>
References: <20051215064740.GD63981 at cfcl.com>
	<20051215140026.GA19716 at fetter.org>
	<20051215191543.GA32539 at nodewarrior.org>
Mime-Version: 1.0 (Apple Message framework v619.2)
Message-Id: <8c4c2b0e58941c341cbab6bcb0adf8cb at fruitfly.org>
From: chris mungall <cjm at fruitfly.org>
Date: Thu, 15 Dec 2005 11:37:40 -0800
To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
X-Mailer: Apple Mail (2.619.2)
X-Virus-Scanned: by amavisd-new using ClamAV at fruitfly.org
Cc: "San Francisco Perl Users' Group" <sfpug at sf.pm.org>
Subject: Re: [sf-perl] [sfpug] Practical theory:  graphs
X-BeenThere: sanfrancisco-pm at pm.org
X-Mailman-Version: 2.1.6
Precedence: list
Reply-To: San Francisco Perl Mongers User Group <sanfrancisco-pm at pm.org>
List-Id: San Francisco Perl Mongers User Group <sanfrancisco-pm.pm.org>
List-Unsubscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=unsubscribe>
List-Archive: <http://mail.pm.org/pipermail/sanfrancisco-pm>
List-Post: <mailto:sanfrancisco-pm at pm.org>
List-Help: <mailto:sanfrancisco-pm-request at pm.org?subject=help>
List-Subscribe: <http://mail.pm.org/mailman/listinfo/sanfrancisco-pm>,
	<mailto:sanfrancisco-pm-request at pm.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: sanfrancisco-pm-bounces at pm.org
Errors-To: sanfrancisco-pm-bounces at pm.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 2319
Lines: 56


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

_______________________________________________
SanFrancisco-pm mailing list
SanFrancisco-pm at pm.org
http://mail.pm.org/mailman/listinfo/sanfrancisco-pm

>From sfpug-owner+M1388 at postgresql.org Thu Dec 15 10:24:45 2005
Return-Path: <sfpug-owner+M1388 at postgresql.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFIOjcP005273
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 10:24:45 -0800
Received: (qmail 20369 invoked by alias); 15 Dec 2005 18:24:46 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 14826 invoked from network); 15 Dec 2005 18:24:45 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 18:24:45 -0000
Received: from mx2.hub.org (mx2.hub.org [200.46.204.254])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFITveg042934
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 10:29:58 -0800 (PST)
	(envelope-from sfpug-owner+M1388 at postgresql.org)
Received: from postgresql.org (postgresql.org [200.46.204.71])
	by mx2.hub.org (Postfix) with ESMTP id 6F4BA512CC7;
	Thu, 15 Dec 2005 18:24:36 +0000 (GMT)
X-Original-To: sfpug-postgresql.org at localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id 549209DCBFD
	for <sfpug-postgresql.org at localhost.postgresql.org>; Thu, 15 Dec 2005 14:24:35 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
 by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
 with ESMTP id 71314-02 for <sfpug-postgresql.org at localhost.postgresql.org>;
 Thu, 15 Dec 2005 14:24:34 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from davinci.ethosmedia.com (server227.ethosmedia.com [209.128.84.227])
	by postgresql.org (Postfix) with ESMTP id C65A09DCA82
	for <sfpug at postgresql.org>; Thu, 15 Dec 2005 14:24:32 -0400 (AST)
X-EthosMedia-Virus-Scanned: no infections found
Received: from [64.81.245.111] (account josh at agliodbs.com HELO [192.168.1.27])
  by davinci.ethosmedia.com (CommuniGate Pro SMTP 4.1.8)
  with ESMTP id 8695011; Thu, 15 Dec 2005 10:27:11 -0800
From: Josh Berkus <josh at agliodbs.com>
Reply-To: josh at agliodbs.com
Organization: Aglio Database Solutions
To: sfpug at postgresql.org
Subject: Re: [sfpug] Practical theory:  graphs
Date: Thu, 15 Dec 2005 10:29:35 -0800
User-Agent: KMail/1.8
Cc: Quinn Weaver <qw at sf.pm.org>
References: <20051215064740.GD63981 at cfcl.com>
In-Reply-To: <20051215064740.GD63981 at cfcl.com>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200512151029.35826.josh at agliodbs.com>
X-Virus-Scanned: by amavisd-new at hub.org
X-Mailing-List: sfpug
List-Archive: <http://archives.postgresql.org/sfpug>
List-Help: <mailto:majordomo at postgresql.org?body=help>
List-ID: <sfpug.postgresql.org>
List-Owner: <mailto:sfpug-owner at postgresql.org>
List-Post: <mailto:sfpug at postgresql.org>
List-Subscribe: <mailto:majordomo at postgresql.org?body=sub%20sfpug>
List-Unsubscribe: <mailto:majordomo at postgresql.org?body=unsub%20sfpug>
Precedence: bulk
Sender: sfpug-owner at postgresql.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 201
Lines: 12

Quinn,

> If anyone can come up with this, I owe them a huge debt of gratitude. :)

Hmmmm ... does Celko's tree book cover graphs?   DF?

-- 
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

>From sfpug-owner+M1389 at postgresql.org Thu Dec 15 10:30:15 2005
Return-Path: <sfpug-owner+M1389 at postgresql.org>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBFIUFdN005367
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 10:30:15 -0800
Received: (qmail 4710 invoked by alias); 15 Dec 2005 18:30:16 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 21771 invoked from network); 15 Dec 2005 18:30:15 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 15 Dec 2005 18:30:15 -0000
Received: from mx1.hub.org (mx1.hub.org [200.46.208.251])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBFIZSeg044756
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 10:35:28 -0800 (PST)
	(envelope-from sfpug-owner+M1389 at postgresql.org)
Received: from postgresql.org (postgresql.org [200.46.204.71])
	by mx1.hub.org (Postfix) with ESMTP id 3380A6531ED;
	Thu, 15 Dec 2005 14:30:12 -0400 (AST)
X-Original-To: sfpug-postgresql.org at localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id C2B5D9DCC14
	for <sfpug-postgresql.org at localhost.postgresql.org>; Thu, 15 Dec 2005 14:30:08 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
 by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
 with ESMTP id 72297-06 for <sfpug-postgresql.org at localhost.postgresql.org>;
 Thu, 15 Dec 2005 14:30:07 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from fetter.org (dsl092-188-065.sfo1.dsl.speakeasy.net [66.92.188.65])
	by postgresql.org (Postfix) with ESMTP id 4E5F09DC980
	for <sfpug at postgresql.org>; Thu, 15 Dec 2005 14:30:05 -0400 (AST)
Received: from fetter.org (localhost.localdomain [127.0.0.1])
	by fetter.org (8.13.4/8.12.10) with ESMTP id jBFIU26V007181;
	Thu, 15 Dec 2005 10:30:03 -0800
Received: (from shackle at localhost)
	by fetter.org (8.13.4/8.13.4/Submit) id jBFIU2sg007180;
	Thu, 15 Dec 2005 10:30:02 -0800
Date: Thu, 15 Dec 2005 10:30:02 -0800
From: David Fetter <david at fetter.org>
To: Josh Berkus <josh at agliodbs.com>
Cc: sfpug at postgresql.org, Quinn Weaver <qw at sf.pm.org>
Subject: Re: [sfpug] Practical theory:  graphs
Message-ID: <20051215183001.GA7089 at fetter.org>
References: <20051215064740.GD63981 at cfcl.com> <200512151029.35826.josh at agliodbs.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <200512151029.35826.josh at agliodbs.com>
User-Agent: Mutt/1.4.2.1i
X-Virus-Scanned: by amavisd-new at hub.org
X-Mailing-List: sfpug
List-Archive: <http://archives.postgresql.org/sfpug>
List-Help: <mailto:majordomo at postgresql.org?body=help>
List-ID: <sfpug.postgresql.org>
List-Owner: <mailto:sfpug-owner at postgresql.org>
List-Post: <mailto:sfpug at postgresql.org>
List-Subscribe: <mailto:majordomo at postgresql.org?body=sub%20sfpug>
List-Unsubscribe: <mailto:majordomo at postgresql.org?body=unsub%20sfpug>
Precedence: bulk
Sender: sfpug-owner at postgresql.org
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 418
Lines: 19

On Thu, Dec 15, 2005 at 10:29:35AM -0800, Josh Berkus wrote:
> Quinn,
> 
> > If anyone can come up with this, I owe them a huge debt of gratitude. :)
> 
> Hmmmm ... does Celko's tree book cover graphs?   DF?

Not really.

IMHO, the tree book is a rehash of his other stuff on trees in SQL for
Smarties, 3rd. Ed.

Cheers,
D
-- 
David Fetter david at fetter.org http://fetter.org/
phone: +1 415 235 3778

Remember to vote!

>From elein at varlena.com Thu Dec 15 17:27:22 2005
Return-Path: <elein at varlena.com>
Received: from server-a114.beigetower.net (bx19.beigetower [192.168.1.254])
	by mail01.beigetower (8.12.11/8.12.11) with SMTP id jBG1RMKk012588
	for <weavqui at mail01.beigetower>; Thu, 15 Dec 2005 17:27:22 -0800
Received: (qmail 16316 invoked by alias); 16 Dec 2005 01:27:22 -0000
Delivered-To: funkspiel.org-quinn at funkspiel.org
Received: (qmail 12745 invoked from network); 16 Dec 2005 01:27:21 -0000
Received: from unknown (HELO cfcl.com) (24.221.172.174)
  by server-a082.beigetower.net with SMTP; 16 Dec 2005 01:27:21 -0000
Received: from a.mail.sonic.net (a.mail.sonic.net [64.142.16.245])
	by cfcl.com (8.12.6/8.12.6) with ESMTP id jBG1Waeg095127
	for <qw at sf.pm.org>; Thu, 15 Dec 2005 17:32:37 -0800 (PST)
	(envelope-from elein at varlena.com)
Received: from localhost.localdomain (64-142-36-103.dsl.static.sonic.net [64.142.36.103])
	by a.mail.sonic.net (8.13.3/8.13.3) with ESMTP id jBG1RD0I024437
	(version=TLSv1/SSLv3 cipher=DES-CBC3-SHA bits=168 verify=NO);
	Thu, 15 Dec 2005 17:27:14 -0800
Received: from elein by localhost.localdomain with local (Exim 4.50)
	id 1En4Hx-0000We-1T; Thu, 15 Dec 2005 17:21:37 -0800
Date: Thu, 15 Dec 2005 17:21:36 -0800
To: Quinn Weaver <qw at sf.pm.org>
Cc: SF Postgres <sfpug at postgresql.org>
Subject: Re: [sfpug] Practical theory:  graphs
Message-ID: <20051216012136.GQ26986 at varlena.com>
Mail-Followup-To: Quinn Weaver <qw at sf.pm.org>,
	SF Postgres <sfpug at postgresql.org>
References: <20051215064740.GD63981 at cfcl.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20051215064740.GD63981 at cfcl.com>
User-Agent: Mutt/1.5.9i
From: elein <elein at varlena.com>
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mail01.beigetower
X-Spam-Level: 
X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO 
	autolearn=unavailable version=3.0.2
Status: RO
Content-Length: 1129
Lines: 33

On Wed, Dec 14, 2005 at 10:47:40PM -0800, Quinn Weaver wrote:
> Hi, all,
> 
> I'm looking for a practical, lay book on graph theory, especially one
> that describes how to represent graphs in RDBMSs.
> 
> I fear I am stuck with something by Date, but... Do people have any
> other recommendations?
> 
> I specifically don't want formal proofs of mathematical properties of
> graphs.  What I want is something more emic: What can you represent
> with x kind of graph?  What are its properties?  What are the
> algorithms for traversing (or otherwise processing it)?  In short,
> what is it good for?
> 
> If anyone can come up with this, I owe them a huge debt of gratitude. :)
> 
> Best regards,
> 
> --
> qw (Quinn Weaver); #President, San Francisco Perl Mongers
> =for information, visit http://sf.pm.org/weblog =cut
> 

I have an article with some algorithms for setting up a tree graph
and traversing it, deleting nodes, etc.  It might help.  I'd be 
interested in hearing what exactly you are trying to do--that would 
lead to more specific suggestions.

http://www.varlena.com/GeneralBits/65.php

--elein
elein at varlena.com



More information about the SanFrancisco-pm mailing list