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

Re: First order logic and SPARQL

From: Pat Hayes <phayes@ihmc.us>
Date: Mon, 6 Sep 2010 11:43:02 -0500
Cc: Semantic Web <semantic-web@w3.org>, public-sparql-dev@w3.org
Message-Id: <9DC784B0-6B34-4D96-849C-7709B7E3B5F5@ihmc.us>
To: Bijan Parsia <bparsia@cs.man.ac.uk>

On Sep 6, 2010, at 3:14 AM, Bijan Parsia wrote:

> On 6 Sep 2010, at 02:29, Pat Hayes wrote:
> [snip]
>> 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.
> 
> That can't be right. I get a non-monotonic consequence relation if I conclude it is true based on its absence.

You conclude negation - falsity of the triple - from a failure to prove it - its absence from the query results. 
> 
>> 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."
> 
> But this is exactly epistemic reflection.

Could be, I'm not sure what *exactly* you mean by this phrase. 

> The fundamental marker of non-monotonic consequence is that for some KB, some assertion (A), and some consequence (C), KB |- C and (KB + A) |\- C, where the plus is simple set-theoretic expansion.

Right.

> NOT EXISTS seems to meet that criterion. The set of answers shrinks as we set theoretically add triples to the graph.

The above definition refers to entailment, however. Nothing in what you say indicates that adding triples will cause any entailment to fail. The set of answers to a given query might shrink, but so what? That isn't non-monotonicity (at least, not in the sense in which that term is used in the field that originated it.)

> You can preserve monotonicity of the consequence relation by treating the "real" KB as some sort of expanded with the consequences (e.g., filling out the "blank" part of the table with explicit nulls). But then, you no longer merely add A, but you also retract the null. But this just shifts the non-monotonicity to insertion time.

Not sure if I follow this talk of 'nulls', but 'shifting the nonmonotonicity' is exactly eliminating the nonmonotonicity. If I *delete* something from a bunch of RDF, its no longer the same RDF graph. Follow through the definitions, and you will have a purely monotonic logic still. 

> 
>> (And similarly for all other uses of !bound trickery.)
> 
> ? !bound says "Entail some answer iff the variable in the graph pattern isn't bound, i.e., there is no corresponding ground entailment".

If it says this, it ought not to. Which 'entailment' is being used here?  Not RDF entailment, for sure. Maybe SPARQL should be understood as a (rather alarmingly expressive) semantic extension to RDF, so that query results have the status of genuine entailments. But that isn't how the specs are written. 

> 
>> 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.
> 
> I don't see that. (Even before, I thought !bound introduced non-monotonicity.)

LIke I say, I don't think it does, if we cleave to the strict meaning of this term. And I agree I am being pedantic, but then semantics is a pedantic business, as Im sure you agree :-)

> 
>> So, Bijan's brain fart was in fact not a fart at all.
> 
> I think it was, even if, contrary to fact, I had gotten the right answer. I was overeager to refute the connection between being commutative and having a formal spec. My bad.
> 
>> The semantics of SPARQL, even with all the tricks and Bob MacGregor's complaints to the contrary,  is perfectly monotonic.
> 
> On 6 Sep 2010, at 07:56, Pat Hayes wrote:
> [snip]
>> I guess it is in a sense, though I'd like to see the example before committing myself. My point however was directed at the assumption that implementing not-exists queries itself made the logic nonmonotonic, which is incorrect.
> 
> The consequence relation which includes, in its consequence language "NOT EXISTS", even in the form you asserted above, has to be non-mon.

But if we think of SPARQL in this way, then it is no longer an RDF query language but instead is defined over some very expressive semantic extension to RDF, one which AFAIK has never been given a model-theretic  semantics. (So that conclusions like this one can be expressed in it.) I think is is a grave mistake to think of it in this way, since it was always intended to be a query language *for RDF*, but whatever. 

> It doesn't make the consequence relation between RDF graphs non-mon (obviously), but one can lose "NOT EXISTS" answers (entailments)

Being an answer is not identical with being an entailment. If you want 'NOT EXISTS' to be an entailment, you have to give truth conditions for it and check the entailment conditions that result. It will get complicated, and you will have to re-think the basic RDF semantic machinery. I don't think that EXISTS is entailed by the simple conjunction of the triples in an RDF graph, for example. 

Pat


> merely by adding statements.
> 
> 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 16:44:00 GMT

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