Re: First order logic and SPARQL

On Sat, Sep 4, 2010 at 11:10 AM, Bob MacGregor <bob.macgregor@gmail.com>wrote:

> I find this statement potentially misleading:
>
>
>         "SPARQL and non-recursive safe Datalog with negation have
> equivalent expressive power, and hence,
>          by classical results, SPARQL is equivalent from an expressiveness
> point of view to Relational Algebra"
>
> SPARQL, to its detriment, does not have a model-theoretic semantics
> (whereas logic languages like CommonLogic
> do).


If I'm not wrong, SPARQL originally didn't have formal semantics defined.
They have been defined in academic papers:

Semantics of SPARQL http://ing.utalca.cl/~jperez/papers/sparql_semantics.pdf
Semantics and Complexity of SPARQL
http://www.dcc.uchile.cl/~cgutierr/papers/sparql.pdf
A SPARQL Semantics based on Datalog
http://www.springerlink.com/content/9608038906030121/


> The most obvious difference is that in logic, the AND operator is
> commutative, while in SPARQL, the
> order of conjuncts in an AND (a ".") makes a difference -- commute them,
> and you sometimes change the
> result/meaning of the query.
>

Really???

>
> My impression is that Datalog is in fact declarative (unlike Prolog).  I
> suppose its possible that a declarative language,
> nrs Datalog wn, and a non-declarative one, SPARQL, could have the same
> expressive power, even though
> they cannot be equated semantically (on the surface, that seems
> counterintuitive).  On the other hand, I'm
> wondering if you have somehow "dressed up" SPARQL to make it more
> principled than it really is to make your
> claim of "equivalence" -- are you talking about the real SPARQL, or some
> idealized version?
>

Page 1, Paragraph 1  of The Expressive Power of SPARQL

"*we compare the expressive power of SPARQL and non-recursive safe Datalog
with negation (nr-Datalog¬). To determine the expressive power of SPARQL,
first, we show –using the above results– that the W3C specification is
equivalent to a well behaved and studied formalization with compositional
semantics, which we will denote in this paper SPARQLC [6]. Then we compare
SPARQLC with nr-Datalog¬. First we show that SPARQLC is contained in
nr-Datalog¬ by defining transformations (for databases, queries, and
solutions) from SPARQLC to nr-Datalog¬, and we prove that the result of
evaluating a SPARQLC query is equivalent, via the transformations, to the
result of evaluat- ing (in nr-Datalog¬) the transformed query. Second, we
show that nr-Datalog¬ is contained in SPARQLC using a similar approach.
These two results prove that nr-Datalog¬ and SPARQLC are equivalent. It is
important to remark that the transformations used are explicit and simple,
and in all steps bag semantics is considered.*"

>
> - Bob
>