Re: First order logic and SPARQL

On 6 Sep 2010, at 17:43, Pat Hayes wrote:

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

? I'm just pointing out that I can conclude it to be *true* from its  
absence and get a non-monotonic relation. This is easy to encode in  
default logic.

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

I mean that I reflect on the structure of the knowledge base,  
similarly to how autoepistemic logic works.

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

Yes. The answers are entailed by the KB.

> Nothing in what you say indicates that adding triples will cause  
> any entailment to fail.

If you don't want to call the answers to the query entailments (in a  
more expressive logic than allowed in the dataset), that's fine. But  
that's what we're talking about.

Indeed, if you allow construct queries to  mutually recurse, you get  
Axel's datalog with stratified negation result.

But I don't see the problem in allowing the language of the  
consequences to be different (either broader or narrower) than the  
language of the dataset. I can query an ontology without counting  
quantifiers using counting quantifiers.

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

We can define a consequence relation (Cn(Gamma, alpha)) wherein the  
language of Gamma is RDF and the language of alpha is SPARQL (or  
perhaps ground instances of SPARQL). This is very familiar to the  
field that originated the term non-mon :)

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

It's shifting. You can rely on the well known correspondence between  
belief revision and nonmonotonic consequence to shift the non- 
mononticinity around. But you haven't eliminated it in any  
interesting way.

Indeed, in this case, you've obscured it. It's pretty clear that  
adding a triple to an RDF graph that does not contain it does not  
retract anything under the standard reading.

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

I'm not sure which spec you're reading, but I read:
	http://www.w3.org/TR/rdf-sparql-query/#sparqlBGPExtend

In any case, the entailment analysis is more or less standard. If you  
want to police the language so we say "Non-monontonic answer sets" or  
some such, well, ok. I don't think it's useful or particularly  
correct or particularly standard (and it's at odds with wide  
literatures, e.g., database), but whatever works for you :) The fact  
of the matter is that the semantics of not bound requires a non- 
monotonic consequence relation or "implicit retraction" (er...which  
seems just non-mon :)). And, in point of fact, you can lose answers  
by adding information to the dataset.


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

I don't think it's a matter of being strict. That is, I don't see a  
reasonable reading which makes "!bound" monotonic.

> And I agree I am being pedantic, but then semantics is a pedantic  
> business, as Im sure you agree :-)

Well, I don't object to pedantry. So let me be clear:

	By "!bound is a non-monotonic operator and thus SPARQL over RDF is  
non-monotonic" I mean that
		if we define a consequence relation between RDF graphs and (e.g.,  
boolean) SPARQL queries
			that consequence relation is non-monotonic under a standard  
reading of RDF graphs and their expansion
If you change RDF graphs so that every triple not entailed by the  
graph is explicitly not in the graph such that adding a triple  
requires retracting it's non-existence, I agree that the consequence  
relation can be monotonic, but then what seems like set theoretic  
addition is, in fact, revision.

[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,

http://www.w3.org/TR/rdf-sparql-query/#sparqlBGPExtend

I'm not sure what you mean by "over". The consequence language is  
differently expressive than the KB language. But that's not too  
surprising.

> one which AFAIK has never been given a model-theretic  semantics.

There's some oddities to how these consequence relations are shaped  
(since we want, e .g., finite answers), but nothing too terribly  
outre as Axel's reduction to Datalog with stratified negation shows.

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

Well, many wanted it to be more and it is more:
	http://www.w3.org/TR/sparql11-entailment/

I don't mean to rehash old battles, but I think this general line of  
analysis holds up pretty well and is proving fruitful.

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

True. An answer is a substitution into a query formula such that the  
grounded query is entailed (perhaps with some side conditions) from  
the KB.

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

I'm not sure what you think the problem is. You may want to read  
Axel's paper.

But seriously, if you prefer to talk about the answers some other  
way, go ahead. The key point is that things are pretty well  
understood to the point that extensions and reductions to other  
(classic) formalisms seem to work out just fine and, in fact, for  
some things in a fairly standard way.

Cheers,
Bijan.

Received on Monday, 6 September 2010 17:28:46 UTC