On 4/2/07, Jorge Pérez <[EMAIL PROTECTED]> 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
