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
