- From: Chimezie Ogbuji <chimezie@gmail.com>
- Date: Fri, 6 Apr 2007 23:02:35 -0400
- To: jperez@ing.puc.cl
- Cc: dev@rdflib.net, "Ivan Herman" <ivan@ivan-herman.net>, public-sparql-dev@w3.org
On 4/2/07, Jorge Pérez <jperez@ing.puc.cl> 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 P.et. 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