Re: FYI: SPARQL Algebra, Reductions, Forms and Mappings for Implementations

On 4/2/07, Jorge Pérez <> wrote:
> Hi,
> > (P1 UNION P2 UNION .... UNION PN) OPT A) OPT B) ... OPT C)
> >
> > I.e., DNF extended with OPTIONAL patterns.
> what kind of operators are allowed in the Pi's in the expression above? if
> the Pi's do not have OPTs then I think that not every pattern is
> equivalent to a pattern in that form.

Yes, they don't have any OPTs and not every pattern can be expressed
in this form (even after rewriting/reordering)   This is a limitation
of the procedural algorithm used (an expansion tree).  However, when
you consider the properties of well-designed UNION-free patterns, you
can cover a large majority.

> > I had asked their thoughts on performance impact on evaluating GRAPH
> > patterns declaratively instead of imperatively (the way they are
> > defined in both the DAWG semantics and the Jorge P. et. al papers) and
> > I'm curious on your thoughts on this as well.

> Surely the naive way of evaluate GRAPH induced by the formal semantics
> will not be very efficient and special purpose tecniques (like the one you
> mention above) would be of help. There are also reordering rules (in the
> spirit of the rules presented in "Semantics and Complexity of SPARQL")
> that hold for GRAPH and that may be a lot of help in optimizing queries
> (for example with GRAPH the DNF still holds).

Ahh yes.

> > Finally, an attempt at a formal mapping from DAWG algebra evaluation
> > operators to the operators outlined in the Jorge al papers is
> > below:
> >
> > merge(μ1,μ2)             = μ1 ∪ μ2
> > Join(Omega1,Omega2)      = Filter(R,Omega1 ⋉ Omega2)
> > Filter(R,Omega)          = [[(P FILTER R)]](D,G)
> > Diff(Omega1,Omega2,R)    = (Omega1 \ Omega2) ∪ {μ | μ in Omega1 ⋉
> > Omega2 and *not* μ |= R}
> > Union(Omega1,Omega2)     = Omega1 ∪ Omega2

> I really dont understand very well what you mean here, soory :-|

No problem.

-- Chimezie

Received on Saturday, 7 April 2007 03:02:38 UTC