Re: First order logic and SPARQL

OK, not wanting to start another flame war about nonmonotonicity, but just for clarification:

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

Indeed, and Im sorry I didn't follow your point here, because I agree with it. But I was thinking of a different point. If (as you say, we can do this) we take the SPARQL conclusion to be written in a new language, which we might call SPARQL-RDF (it doesn't make sense to say SPARQL, since it has to be an assertional language) then the truth conditions for this language have to face up to the fact that it refers to RDF graphs (by name, in some cases, but always to some RDF graph) and asserts things about them, like that they have or do not have triples in them. An RDF graph is a set of triples. Adding a triple to a set creates a *different* set. So when we start talking about monotonicity, we need to be very careful what it means to add a triple to a graph. In RDF this is simply conjunction, but if the language itself can talk about these sets of triples, then adding a triple to the antecedent graph is a lot more than a simple logical conjunction: it involves a change to the antecedent. This is what I meant by deleting something: again, I apologise for the misleading carelessness in my expression. I wasn't thinking about 'nulls', which I agree is just another kind of nonmonotonicity. (I think I am talking about what you call epistemic reflection, by the way, though that term is too slippery to be used with confidence.) 

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

So was I. That was written to cover the possibility of extending SPARQL to things like OWL entailment. To use this for SPARQL/RDF entailment requires someone to first give truth conditions for SPARQL/RDF.  Maybe someone has done this: I would be very interested to see it. 

> 
> In any case, the entailment analysis is more or less standard.

I think not. At the very least it would require a model theory for epistemic reflection.

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

You can lose answers; well, you lose some and you gain some. But I don't think you lose any entailments, if you state the truth conditions fully. Adding information *changes* the dataset, which the answer *refers to*.  It's not a simple conjunction of new information any more. 

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

Its the one where you agree that a dataset really is a *set*, not a thing with state which can retain its identity while having information added to it. 

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

I dont want to make that change, but I still disagree that the consequence relation is nonmonotonic, if you state the truth conditions for the SPARQL conclusion precisely, and in a form which acknowledges the specs requirements that an RDF graph (note the singular) is a *set* of triples. And of course that adding something to a set gives you a new set, not the original set 'enlarged'. 

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

But it does have its problems, such as hallucinations of nonmonotonicity... :-)

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

My point was less pedantic :-). There can be entailments which are not (associated with) answers. Being entailed (in the above sense) is a necessary condition on an answer, but not a sufficient one.  SPARQL itself omits many entailments from its answer sets. So when the set of answers becomes smaller, it does not automatically mean that the set of entailments has shrunk. 

Pat


------------------------------------------------------------
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 Wednesday, 8 September 2010 15:00:01 UTC