[Haskell-cafe] OT: representations for graphs

[Bayley, Alistair]

(OT, but I'm hoping some of you might have some ideas on this anyway...)

I was wondering what alternative representations there are for graphs,
or maybe if there might be a way to derive one/some from some insightful
observations. For the purposes of storing and exmaining (querying)
graphs in an SQL database.

For example, a tree (so, a specialised sub-class of graph) can be
represented by a three models, that I know of:
 - adjacency-list (the most common)
 - materialised-path (a denormalisation of adjacency-list)
 - nested-sets

Nested-sets (and materialised-path) works for trees because the graph is
 - directed (so we know which nodes are parents or children)
 - acyclic (there's a definite root, and leaves)
 - every child has a single parent (so no diamond shapes - does this
property have a name?)

Nested-sets works well with SQL databases for querying, at the expense
of updates. Adjacency-list is easier to update, but some queries suck,
or are downright impossible in normal SQL.

We can use the adjacency-list model for graphs too, but it has the same
query deficiencies as for trees. I'd like some sort of alternative to
adjacency-list, like nested-sets, that would work better for querying at
the expense of updates.

Alistair
*****************************************************************
Confidentiality Note: The information contained in this message,
and any attachments, may contain confidential and/or privileged
material. It is intended solely for the person(s) or entity to
which it is addressed. Any review, retransmission, dissemination,
or taking of any action in reliance upon this information by
persons or entities other than the intended recipient(s) is
prohibited. If you received this in error, please contact the
sender and delete the material from any computer.
*****************************************************************