Implementing a graph algebra
- From: amado.alves@xxxxxxxxxx
- Date: 8 Nov 2005 13:03:49 -0800
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
.
- Follow-Ups:
- Re: Implementing a graph algebra
- From: JOG
- Re: Implementing a graph algebra
- Prev by Date: Re: Nested Sets vs. Nested Intervals
- Next by Date: Re: Nested Sets vs. Nested Intervals
- Previous by thread: union all vs. left outer join
- Next by thread: Re: Implementing a graph algebra
- Index(es):
Relevant Pages
|
