Re: Implementing a graph algebra

amado.alves_at_netcabo.pt wrote:
> Dear database theorists:
>
> I am implementing a graph algebra designed to serve as the query plan
> component of a graph-based database system. I'm looking for ways to
> optimize certain cases explained below.
>
> The algebraic type is the set of vertices. The operations include the
> set theoretic operations and an adjacency operator A(X) with the
> obvious semantics:
>
> A(X) = {y : x in X, {x, y} is an edge in the graph}
>
> I have been able to optimize the resolution of expressions like (^ =
> intersection)
>
> A(K)
> A(K1) ^ ... ^ A(Kn)
>
> where Ki is a known set, usually the singleton of a known vertex. I'm
> looking for ways to optimize expressions of higher order e.g.
>
> A(A(K))
> A(A(K1)) ^ ...
>
> I'm particularly interested in the intersection operation, as it shows
> up a lot in expressions derived from concrete cases of data modelling
> and querying (Biopathways, XMark, XQuery Use Cases).
>
> /*
> The description above is a slight simplification. The real case is a
> directed graph, so we have source and target adjacency S, T instead of
> just A, and hence expressions like
>
> S(K1) ^ T(K2) ^ ...
> S(S(K))
> S(T(K))
>
> Naturally A(X) = S(X) U T(X). S, T are sometimes notated A+, A- in the
> literature (or the other way around, and that's why I don't use the +/-
>
> notation, lack of obvious metaphor).
>
> Also, my system has vertex order, which is used in the algebraic sets
> to optimize certain operations namely ^.
> */
>
> Thanks a lot,
> Marius A. Alves
> PhD student, University of Porto

Marius,

This is obviously more to do with graph theory than database theory, which operates at a different conceptual level (and I believe the confusion of these different architectural levels is the root cause of trouble in any corresponding debate). However, It is of course quite possible for a higher level database model to utilise a lower level graph encoding, and as such I find your algebra interesting.

However I imagine there exists a copious amount of work already done in this area, and wonder if a good place to receive feedback your work would be places such as the c++ boost::graph library forums, which is, afaik, currently the most active area for this topic. Research wise I understand that it is also a focus of the web and more specifically "hypertext" field, which tends to view a graph as the conceptual model as well internal mechanism.

Jim. Received on Mon Nov 21 2005 - 13:20:09 CET