W3C home > Mailing lists > Public > semantic-web@w3.org > September 2010

Re: First order logic and SPARQL

From: Juan Sequeda <juanfederico@gmail.com>
Date: Sat, 4 Sep 2010 14:20:46 -0500
Message-ID: <AANLkTik0iAo83323nQFmDL6=1ijsEa+o9xs3xAaMqXVo@mail.gmail.com>
To: Bob MacGregor <bob.macgregor@gmail.com>
Cc: Jitao Yang <jitao.yang@gmail.com>, semantic-web@w3.org, public-sparql-dev@w3.org
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
A SPARQL Semantics based on Datalog

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


> 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
Received on Saturday, 4 September 2010 19:21:40 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:42:22 UTC