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

Re: First order logic and SPARQL

From: Pat Hayes <phayes@ihmc.us>
Date: Sun, 5 Sep 2010 20:29:15 -0500
Cc: Bijan Parsia <bparsia@cs.man.ac.uk>, "Bob MacGregor" <bob.macgregor@gmail.com>, "Juan Sequeda" <juanfederico@gmail.com>, "Jitao Yang" <jitao.yang@gmail.com>, <semantic-web@w3.org>, <public-sparql-dev@w3.org>
Message-Id: <673434A1-7590-4A41-8598-8C5F6B9FCE52@ihmc.us>
To: Axel Polleres <axel.polleres@deri.org>

On Sep 5, 2010, at 10:17 AM, Axel Polleres wrote:

>>> The problem with SPARQL stems from the OPTIONAL operator.  A mantra 
>>> of RDF has been that it
>>> has open world semantics.  The OPTIONAL operator is inherently non-
>>> monotonic.
>> 
>> ?? I don't think so. I'd be interested in a reference.
> 
> Obviously OPTIONAL is nonmomotonic and in fact, NOT EXISTS can be emulated not only 
> with the widely known OPTIONAL + FILTER !Bound() trick (see [1] Query #13 for an example),
> but you actually don't need the FILTER even (see Query #14 in the same tutorial [1]).
> 
> In SPARQL 1.1 we will very likelty have explicit MINUS/NOT EXISTS operators such that 
> you don't need those tricks anymore to model negation, see [2] Queries #16, #16b, 16#c.  
> 
> (Thanks Lee for his excellent tutorials, BTW!) 
> 
> Axel
> 
> 1. http://personnel.univ-reunion.fr/fred/Enseignement/SW/SPARQL-by-example/
> 2. http://www.cambridgesemantics.com/2008/09/sparql-by-example/
> 
> 
> 
> On 5 Sep 2010, at 15:21, Bijan Parsia wrote:
> 
>> On 5 Sep 2010, at 02:29, Bob MacGregor wrote:
>> [snip]
>>> 
>>> Yes, really.  It sounds very much like you have defined/referenced a 
>>> cleaned-up version of SPARQL which
>>> unfortunately does not reflect the real-world semantics.
>> 
>> http://www.w3.org/TR/rdf-sparql-query/#sparqlDefinition
>> 
>> The semantics of (a good chunk) of the algebra is in terms of the 
>> relational algebra.
>> 
>> The formalization is based on this paper:
>>        http://arxiv.org/pdf/cs/0605124v1
>> 
>> I wouldn't conflated declarative (or formal) semantics with model 
>> theoretic.
>> 
>>> The problem with SPARQL stems from the OPTIONAL operator.  A mantra 
>>> of RDF has been that it
>>> has open world semantics.  The OPTIONAL operator is inherently non-
>>> monotonic.
>> 
>> ?? I don't think so. I'd be interested in a reference.
> 
> Obviously OPTIONAL is nonmomotonic and in fact, NOT EXISTS can be emulated not only 
> with the widely known OPTIONAL + FILTER !Bound() trick, but also 

This is NOT non-monotonic. The NOT EXISTS conclusion that a triple does not occur in an identified RDF graph is a perfectly monotonic inference. It becomes non-monotonic only when you go on to conclude that if said triple does not occur there, it is false. However, neither RDF nor SPARQL supports this further conclusion. Thus, while the SPARQL in query #13 in [1] is (of course) correct, the English gloss given to is subtly incorrect. What that query asks is not, as Lee claims, "Find me members of the Senate Armed Service committee's Strategic Forces subcommittee who do not also serve on the Personnel subcommittee.", but rather ""Find me members of the Senate Armed Service committee's Strategic Forces subcommittee who are not listed in the Personnel subcommittee RDF graph." (And similarly for all other uses of !bound trickery.) Now, of course, I am being pendantic, since we all know that this RDF graph is complete, so that if someone isn't listed there, then they aren't serving on the subcommittee. But *that* inference is not part of the RDF graph, is not represented by the RDF graph, s not justified by the semantics of the RDF graph, and is not used by the SPARQL machinery or justified by the SPARQL semantics.

So, Bijan's brain fart was in fact not a fart at all. The semantics of SPARQL, even with all the tricks and Bob MacGregor's complaints to the contrary,  is perfectly monotonic. 

Pat Hayes

> 
>> 
>> Note that non-communitivity doesn't imply non-monotinicity. After all, 
>> implication is non-communitive. Optional is defined in terms of left-
>> outer join.
>> 
>>> A few of us devised
>>> a closed-world semantics for OPTIONAL, but the open-world advocates 
>>> rejected the notion, favoring instead
>>> a procedural semantics.
>> 
>> The meaning is the meaning, regardless of the presentation of that 
>> semantics.
>> 
>>> Not only are arguments to OPTIONAL defined to be order-dependent 
>>> (analogous to a series
>>> of if-then-else clauses),
>> 
>> Like implications in first order logic.
>> 
>>> but the SPARQL AND operator became polluted as well -- changing the 
>>> order of conjuncts
>>> that contain OPTIONALs can change the semantics of a SPARQL query.  
>>> I don't have examples available
>>> on the tip of my tongue, but a talk I gave a year ago at SEMTECH had 
>>> an example, and there are many
>>> others out there who should be able to furnish examples.
>> 
>> Can we dig this out?
>> 
>>> It would be a great service to the RDF community if you or someone 
>>> would propose a semantically
>>> well-founded variant of SPARQL (call it SPARQLL for "logical 
>>> SPARQL", or whatever).
>> 
>> I think that's called SPARQL/1.0.
>> 
>>> It would necessarily
>>> have closed-world semantics (as does Datalog).
>> 
>> Well, unbound requires epistemic reflection, but I don't think 
>> OPTIONAL does per se.
>> 
>> There's a lot of tricky parts of any query language because of e.g., 
>> the need to report and control answers. It's perfectly reasonable to 
>> quarrel with choices you don't like, but I think we should be a bit 
>> more careful about the source of the problems. SPARQL/1.0 has a pretty 
>> reasonable and standard formalization.
>> 
>> Cheers,
>> Bijan.
>> 
>> 
> 
> 
> 

------------------------------------------------------------
IHMC                                     (850)434 8903 or (650)494 3973   
40 South Alcaniz St.           (850)202 4416   office
Pensacola                            (850)202 4440   fax
FL 32502                              (850)291 0667   mobile
phayesAT-SIGNihmc.us       http://www.ihmc.us/users/phayes
Received on Monday, 6 September 2010 01:31:02 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 21:45:37 GMT