- From: Pat Hayes <phayes@ihmc.us>
- Date: Thu, 9 Sep 2010 11:05:49 -0500
- To: Bijan Parsia <bparsia@cs.man.ac.uk>
- Cc: www-archive@w3.org
On Sep 9, 2010, at 6:44 AM, Bijan Parsia wrote:
> On 8 Sep 2010, at 15:58, Pat Hayes wrote:
>
>> OK, not wanting to start another flame war about nonmonotonicity, but just for clarification:
>
> Let's see if adding my message to this thread retracts that desire...
>
> I think you've tied yourself up in knots for no good reason.
Could be.
> The semantics of SPARQL (by which I mean the set of triples <Dataset, Query, Answers> sanctioned by the specification wrt RDF datasets)
Ah. I didn't mean that. I meant a model theory, providing truth conditions relative to an interpretation drawn from a set of possible interpretations.
> is rather well specified (with some exceptions, e.g., DESCRIBE). In the spec, this set is described primarily in terms of an algebra which is pretty much the relational algebra. Equivalently, Axel has shown that it can be described in terms of entailment in (nonrecursive, I would think for simple entailment and SPARQL1.0) Datalog with stratified negation (well, I guess it's automatically stratified :)). If you conceptualize the triple as an axiom schema such that Dataset |- Grounding(Query, Answer) (where Answer is drawn from the set of answers), then we have a clear consequence relation (or something reasonably modeled by a consequence relation). This consequence relation is clearly non-monotonic.
That is, yes. But monotonicity is traditionally defined in terms of entailment, which refers to truth.
>
> I would go further and say that this is a bog-standard and very useful way to conceptualize and reason about the situation (e.g., complexity results fall out very naturally as do implementation techniques). There are other ways of conceptualizing it, but they need to capture the same feature, to wit, there are cases where when you extend a Dataset with an additional triple, you lose "an answer", i.e. a consequence.
>
> It's useful, even if you don't find it congenial, to talk this way even if we didn't have a plethora of model theoretic techniques to cope with it. Default logic was understandable without a model theoretical account
Actually I disagree. The general idea was of course understood intuitively, but there was a jumble of confusion, with many varieties and subspecies of defaultitude, all loosely based on linguistic intuitions, none of them clearly better or worse than any other. Just as there was, much earlier, for tense logics and modal logics generally. In both cases, it was the development of a model theory that cleared up the mess.
> (and, indeed, for many variants, esp. as we get more expressive, it's an ongoing challenge to find any, much less a useful, model theoretic account).
>
> ...
>>> 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)
>
> I'm not sure why you feel this is important. But I don't think we have to go "assertional", at least as I understand it.
Well, monotonicity is defined in terms of entailment which is defined in terms of truth. But I see now that you have been using 'consequence' as distinct from 'entailment' throughout.
> Yes, of course, SPARQL in some sense "asserts" stuff about various RDF KBs. But SPARQL doesn't allow you to assert things (as we currently use it) about other SPARQL queries. That is, we only see SPARQL in consequents (just as in the relational calculus we only see certain constructs in the consequents). It's pretty common to say that this makes SPARQL a query language :)
I agree: I thought this idea - of treating SPARQL as an assertion language - was what *you* were urging.
>
> (Note that we don't have a deduction theorem. We have no object level mechanism for turning an implication (I use this to emphasize the inferential rather than semantic guise we're using) into a conditional in the object language.
>
> We can, of course do this. But then we're into a more full blow rule language (as Axel has done time and again, and well).
>
>> 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.
>
> The data set language (RDF) does not do this. SPARQL does do this (e.g., with !bound, and also with the somewhat odd case of GRAPH variables, but let's put them aside).
>
>> An RDF graph is a set of triples. Adding a triple to a set creates a *different* set.
>
> But doesn't change the query.
It changes what the query refers to, so it does change the query, implicitly. The query always refers to the query graph. Adding a triple to that graph gives a different graph. That means that the query itself has changed in what it refers to.
>
>> 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.
>
> Pat, I think you got a bit lost here. If I have the propositional formula A and A |- B and then I conjoin something to A, e.g., to form A&C, then, well, I have a change to the antecedent. Trivially, right?
Right, but that trivial sense is not what I meant. My point is that if B itself refers to A, and if conjoining C to A *also* changes this reference to refer to (A & C) rather than A, then B has also changed. So the correct way to describe the result is not (A & C) |- B but rather (A & C) |- B', where B' looks very similar to B but means something subtly different. Take the example from the tutorial previously cited: it uses a URI (in the query) which refers to a list of members of a committee. If this is a 'cool URI', this list should never change. But it will, no doubt, as time goes by. Adding someone to the list will cause the query to yield fewer results, indeed. The query has not changed syntactically, but it has changed in what it says, because it now uses the same URI to refer to a different RDF graph - a violation of the RDF named graph model theory. If we were to insist that this kind of uncool URI shifting never occurs, we would need to use a new URI for the changed committee membership list; then the query would have changed, and the non-nonmonotonicity would be apparent.
> The question is what sort of change and what happens as a result of that change. In a monotonic logic if A |- B. then so with A&C |-B. an {A,C} |- B.
See above.
>
>> This is what I meant by deleting something: again, I apologise for the misleading carelessness in my expression.
>
> Even if I conceptualize adding a conjunction as "Deleting A and then adding A&C", or "Deleting {A} and adding {A,C}" it is still the case that these formula have a specific relation which I shall imprecisely characterise as "A" is a subset of "A&C" (from the correspondence in our logics between "A&C" and {A,C}. What we don't have is any assertions of the form "C is not asserted (or implied)". That is, "A" is not shorthand for {A, C is not asserted, or implied}.
I entirely agree. That whole line of thinking is aside from my point.
> It is *true* that "C is not asserted (or implied)" which is why the query ~KC (where K is an epistemic operator) evaluates to true against that KB. That query is evaluated to *false* against A&C or {A,C}. That is, ~KC is not entailed/implied/a consequence of the KB. The entailment relation |- characterized as a set of pairs <KB, Qs> where Q is ground and evaluates to "True" against the KB contains <{A}, ~KC> but not <{A,C}, ~KC> nor <{A&C}, ~KC>. Thus, the consequence relation is not monotonic. For some KB, there is a KB' such that KB is a strict subset of KB' and where <KB, Q> is in |- whereas <KB, Q'> is not in |-.
>
> If I changed my logic so that I could only write what I currently write as {A} as {A, C is not asserted or implied}, then, assuming a fairly standard entailment relation (e.g., non-paracosnistent), I couldn't get to *not* entailing ~KC by merely adding things. I'd need to delete "C is not asserted or implied". But that's really not the logic we have. The fact that "C is not asserted or implied" is not syntactically manifest is precisely what puts the non-monotonicity into the entailment relation rather than into the expansion operation.
>
> (I strongly recommend Makinson's "Bridges from classical to non-monotonic logic". Very illuminating.)
>
>> 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.)
>
> I don't see how it's slippery in this case or what one wouldn't be confident about it.
> [snip]
>> 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.
>
> Perhaps you would be happy to replace "entailment" with "implication"? In any case, Axel has done this and pointed to his paper many times. Reduce to Datalog with stratified negation and the use any of the standard preferred model semantics (since they coincide there).
>
>> Maybe someone has done this: I would be very interested to see it.
>
> See Axel's paper.
>
>>> 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.
>
> I suspect the sticking point is that you want to reserve "entailment" for the semantic consequence relation.
Um, yes. I believe that is what the word means.
> Fine. We do have that (see Axel's paper).
>
> But we don't need it to describe a non-monotonic consequence relation. See the characterization of default logic in terms of fixed point equations (just for extensions! then we have whether we go for brave or cautious reasoning).
>
>>> 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.
>
> Would you be happy if we said we lose consequences? We also lose entailments wrt Datalog semantics.
>
>> Adding information *changes* the dataset, which the answer *refers to*. It's not a simple conjunction of new information any more.
>
> See above. It seems very odd to think that because the *question* is more sophisticated we've changed the *data*.
Well, I think "the data" is changed as soon as anything has the ability to refer to the data and talk *about* it rather than simply draw conclusions *from* it. If I can do something as simple as count the number of triples in a graph, its not just RDF any more.
>
> Another way to see it is that the query language is asking "Does C hold in the e.g., minimal model of the KB"? I don't have to change the KB. But the consequence relation which characterizes this query language is definitely nonmonotonic.
>
>>>>>> 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.
>
> As should be clear above, no one is appealing to stateful things.
Are you sure? Isn't the 'query set' something that can grow or shrink, so not actually a set?
> The nonmonotonicity is expressed in terms of relations between *sets* not in terms of mutation.
>
>>>> 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'.
>
> I really don't know where you're getting that from.
That last sentence is plain old set theory. A union B =/= A, unless B is a subset of A already.
> By "expansion" I mean the belief revision theory operation (http://en.wikipedia.org/wiki/Belief_revision) which does not involve mutation.
? Of course it does. Any change to a set is a "mutation".
>
> [snip]
>>> 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... :-)
>
> I really hope at this point you see that there's no hallucination.
>
> OTOH, I don't know why the question wasn't immediately settled when Axel pointed to his paper which showed an answer preserving reduction from SPARQL 1.0 to Datalog with stratified negation.
Basically because Im not very interested in Datalog semantics, and indeed feel like I ought to use scare quotes when typing that phrase. But I agree this isn't a very persuasive point to make in a public debate.
> That just seems to answer every point you might make.
>
>>>>> 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.
>
> Sure, but then that's a different consequence relation. I can define consequence relations using the RDF model theory in a number of ways:
>
> A) I can restrict the syntactic form of the consequences
> B) I can change how the consequence relation is sensitive to the semantics of the graphs
> E.g., finite vs. infinite models
> Minimal vs. all models
> C) I can extend the syntactic form of the consequences
> I can make the extended syntax sensitive to various aspects of the RDF models (i.e., combine with B)
> E.g., I can count successor nodes in a relational structure.
> I can pay attention to certain classes of model (as above).
> Given a "standard" consequence relation (say, simple entailment), I can use these techniques to define a supra-standard (has more consequences) or sub-standard standard (has fewer consequences) relation or suprasub (missing some and adding some). Furthermore, if I have a supra relation, i can change the monotonicity of the relation wrt to the added consequences while leaving the "classical" or "standard" consequences alone. See (propositional) default logic.
>
> It's reasonable to regard sparql as characterizing a supra-sub relation. We restrict some cosnequences (e.g., so that any particular query characterizes at most a finite number of answers) and we extend others (by having a construct with is sensitive to non-entailment, e.g., !bound). Those extended consequences can increase *or decrease* when the queried against KB merely increases (that is, we replace it with a superset).
>
> Thus, again, that consequence relation is non-monotonic.
Ah, I see. True, of course, nonmonotonicity comes cheap when you take this much freedom to tinker with consequences. I was, all along, intending to refer to monotonicity with respect to a genuine entailment relation, where entailment is defined in terms of truth conditions. Anything else is just computational hacking on top of the actual semantics (which is fine: some of my best friends do it; but it isn't entailment.)
Pat
>
>> 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.
>
> I agree that the set of simple entailments of a dataset increases as the dataset increases. But, just as obviously, simple entailment alone doesn't characterize SPARQL. Similarly in propositional default logic, the set of *classical* consequences never shrinks as you extend the classical portion of the KB. But the defaultly inferred consequences *can*.
>
> These facts are pretty central facts about optional and !bound.
>
> 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 Thursday, 9 September 2010 16:06:45 UTC