Re: First order logic and SPARQL

Dear Pat, 

> The semantics of an algebra? I have no idea what you mean by this. Does this algebra have a model theory?

SPARQL's semantics is defined in the spec in terms of the SPARQL algebra... if you don't like that, the academic works cited earlier in this thread, particularly [1], have translated this algebra to stratified Datalog with negation as failure; as you surely know, all estavlished model-theoretic semantics for this non-monotonic formalism, i.e. perfect model semantics, stable model semantics and well-founded semantics co-incide on stratified programs.

> As I understand SPARQL, the basic entailment against which it is defined is RDF entailment,

Strictly speaking no, the semantics of SPARQL is defined in the spec on top of simple entailment rather than on top of RDF entailment, we are working at the moment in SPARQL1.1 on higher entailment regimes for SPARQL, cf. [2]

> which is (as you say) monotonic. I fail to see how any query process can make a monotonic logic non-monotonic.

by (also shown in [1]) having exactly the same expressivity as Datalog with stratified negation.

best,
Axel

1. Renzo Angles, Claudio Gutierrez: The Expressive Power of SPARQL. International Semantic Web Conference 2008: 114-129
2. http://www.w3.org/TR/sparql11-entailment/

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

> 
> On Sep 6, 2010, at 7:31 AM, Axel Polleres wrote:
> 
> >
> > On 6 Sep 2010, at 02:29, Pat Hayes wrote:
> >
> >>
> >> 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.
> >
> >
> > The *answers* to queries with OPTIONAL can be non-monotonic...
> >
> >
> >> 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."
> >
> > ... yes ...
> >
> >> (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.
> >
> > ... I am not saying that RDF is non-monotonic, but I am saying the semantics of SPARQL's algebra is... not more, not less.
> 
> The semantics of an algebra? I have no idea what you mean by this. Does this algebra have a model theory?
> >
> >>
> >> 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.
> >
> > no: if I add more data (triples) and get less answers, that's - in my understanding of the term - non-monotonic.
> 
> Not in mine, unless you identify 'answer' with 'entailment', this latter being defined model-theoretically. Monotonicity is the condition that if A entails B then (A & C) entails B. Entails, note. When a NOT EXISTS query is run against an RDF graph, what exactly is the relationship between the graph and the query answer? Is the answer *entailed* by the RDF graph? Using what notion of entailment?
> 
> > So, I am not sure what you mean exactly by "perfectly monotonic" then? Can you elaborate?
> 
> As I understand SPARQL, the basic entailment against which it is defined is RDF entailment, which is (as you say) monotonic. I fail to see how any query process can make a monotonic logic non-monotonic.
> 
> Pat
> 
> >
> > thanks,
> > Axel
> >
> >
> >
> >>
> >> 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
> >>
> >>
> >>
> >>
> >>
> >>
> >
> >
> 
> ------------------------------------------------------------
> 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 19:32:47 UTC