- 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