Implementing a graph algebra
Date: 8 Nov 2005 13:03:49 -0800
Message-ID: <1131483829.458403.49030_at_z14g2000cwz.googlegroups.com>
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))
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).
/*
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,
A(A(K1)) ^ ...
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))
PhD student, University of Porto
Received on Tue Nov 08 2005 - 22:03:49 CET