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

Hi,

Chimezie Ogbuji wrote:
> Jorge.
>
> I've been gearing up to an attempt at implementing the Compositional
> SPARQL semantics expressed in both the 'Semantics of SPARQL' and
> 'Semantics and Complexity of SPARQL' papers with the goal of reusing
> existing sparql-p which already implements much of the evaluation
> semantics.  Some intermediate goals are were neccessary for the first
> attempt at such a design [1]:
>
> - Incorporate rewrite rules outlined in the current DAWG SPARQL WD
> - Incorporate reduction to Disjunctive Normal Form outlined in
> 'Semantics and Complexity of SPARQL'
> - Formalize a mapping *from* the DAWG algebra notation to that
> outlined in 'Semantics of SPARQL'
> - Formalize a mapping *from* the compositional semantics to sparql-p
> methods
>
> In attempting to formalize the above mappings I noticed some
> interesting parallels that I thought you and Ivan might be interested
> in (given the amount independent, effort that was put into both the
> formal semantics and the implementations).  In particular
>
> The proposed disjunctive normal form of SPARQL patterns coincides
> directly with the 'query' API of sparql-p [2] which essentially
> implements evaluation of SPARQL patterns of the form:
>
> (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.

>
> In addition, I had suggested [3] to the DAWG that they consider
> formalizing a function symbol which relates a set of triples to the
> IRIs of the graphs in which they are contained.  As Richard Newman
> points out, this is implemented [4] by most RDF stores and in RDFLib
> in particular by the ConjunctiveGraph.contexts method:
>
> contexts((s,p,o)) -> {uri1,uri2,...}

I think that it is not neccesary for formal semantics definitions, but it
may be of help in implementations.

>
> 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).

>
> 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 :-|

- jorge

> Your comments would be greatly appreciated as valuable feedback in
> trying to reconcile the two (somewhat) separate formal semantics with
> *actual* implementations sparql-p and RDFLib.
>
> [1]
> https://svn.rdflib.net/trunk/rdflib/sparql/bison/CompositionalEvaluation.py
> [2]
> http://dev.w3.org/cvsweb/~checkout~/2004/PythonLib-IH/Doc/Attic/pythondoc-sparql.html?rev=1.5&content-type=text/html;%20charset=iso-8859-1#sparql.SPARQL.query-method
> [3]
> http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2007Mar/0000.html
> [4]
> http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2007Mar/0001.html
>
> - Chimezie Ogbuji
>

Received on Monday, 2 April 2007 14:39:34 UTC