From: Axel Polleres <axel.polleres@deri.org>

Date: Fri, 18 Sep 2009 19:07:29 +0100

Message-Id: <861D44B8-74A6-43EE-BD60-A8070A9A6756@deri.org>

To: public-rdf-dawg-comments@w3.org

Date: Fri, 18 Sep 2009 19:07:29 +0100

Message-Id: <861D44B8-74A6-43EE-BD60-A8070A9A6756@deri.org>

To: public-rdf-dawg-comments@w3.org

With permission of Michael Schmidt, I forward an interesting conversation about the expressibility of general negation in current SPARQL... see below. Axel Begin forwarded message: > From: Axel Polleres <axel.polleres@deri.org> > Date: 17 September 2009 18:02:06 GMT+01:00 > To: Michael Schmidt <mschmidt@informatik.uni-freiburg.de> > Cc: <axel@polleres.net>, "Claudio Gutierrez" <cgutierr@dcc.uchile.cl> > Subject: Re: Expressive Power of SPARQL > > short comment (longer answer later...) > > > A MINUS B == (A OPT (B AND (?x,?y,?z))) FILTER (!bnd(?x)) > > you can probably use a trick here using an auxiliary graph in the > named graphs in the dataset to provide the nexessary bindings. > > take > > G_aux =( [] rdf:type [] ) > > i.e. a named graph that just consists of a single triple > > Then your query > > A MINUS B > > over data set > > D = ( G_def, (G_1, ... G_n) ) > > can be rewritten to > > (A OPT (B AND GRAPH G_aux (?x,?y,?z))) FILTER (!bnd(?x)) > > over data set > > D = ( G_def, (G_1, ... G_n, G_aux) ) > > would that work for you? > > Remark: I proposed a similar trick to encode negation without the > necessity of a BOUND Filter, cf. > > http://lists.w3.org/Archives/Public/public-sparql-dev/2008JulSep/0048.html > > best, > Axel > > On 17 Sep 2009, at 16:40, Michael Schmidt wrote: > >> Hi Axel, >> >> I had some fruitful discussions on the expressiveness of SPARQL with >> Claudio Gutierrez some weeks ago and he proposed to inform you on >> this discussion (given that you are actively involved in the W3C >> activity). >> >> The starting point for our discussion was that I wanted to show >> that every >> first-order constraint can be encoded in SPARQL and ran into trouble >> (although the result that SPARQL has the same expressiveness as >> relational >> algebra implies that it also has the same expressiveness as first- >> order >> logic). In the course of our discussion, we observed two things. >> >> 1.) Encoding of negation >> In Claudio's and Renzo's publication "The expressive power of >> SPARQL", >> it is shown that a syntactic MINUS operator can always be simulated >> by means of the remaining operators. Unfortunately, the construction >> with the copy pattern proposed there fails for expressions A MINUS B >> where B is a variable-free expression. An alternative way to >> implement >> this (which was used by Claudio in recent work and was also the way >> I mentioned during the discussion) is the encoding >> >> A MINUS B == (A OPT (B AND (?x,?y,?z))) FILTER (!bnd(?x)) >> >> where ?x, ?y, ?z are fresh variables. This encoding, however, does >> not work in the general case. To give a counterexample, assume >> that A={}, B={} and D={} (i.e., the empty document D and A, B are >> empty graph patterns). Then >> >> [[{} MINUS {}]]_D = {}, but >> [[({} OPT ({} AND (?x,?y,?z))) FILTER (!bnd(?x))]]_D = {{}} >> >> In fact, the problem occurs only on the empty document and if B is >> identical to or contains the empty graph pattern (if we forbid empty >> graph patterns in B the equivalence holds). >> >> I had some thoughts on this after the discussion with Claudio and >> I actually do not see how to fix the encoding in the general case. >> It seems to me that operator MINUS cannot generally be encoded in >> fragments where the empty graph is present (yet a proof of this >> conjecture is outstanding). While this all may sound very >> theoretical, >> it has some practical implications: I did not succeed in showing how >> to encode first-order constraints in SPARQL without operator MINUS. >> >> >> 2.) Constants in Datalog/SPARQL >> Concerning the encoding of Datalog in SPARQL, there were also some >> interesting observations concerning constants. Consider the Datalog >> query >> >> ans(x) <- c=x. >> >> The answer to this query is always "c", but in SPARQL we cannot >> write such >> a query, because there is no way to produce constants that are not >> contained >> in the domain. In fact, the Datalog-to-SPARQL encoding Claudio >> proposed >> fails for such queries (but we both believe that the encoding can >> be fixed, >> by somehow integrating the domain in the encoding). >> >> The interesting thing is that in my work on encoding first-order >> logic constraints >> in SPARQL I ran into similar problems. What I did - and what would >> be an interesting >> and straightforward extension for SPARQL - is to extend SPARQL by >> so-called >> "constant patterns", which we represent as expressions of the form t >> (?x -> "c") with >> semantics [[t(?x -> "c")]] = {{?x->"c"}} (independent from the >> input document). >> To give an example, the query Q:= >> >> SELECT ?p ?status >> WHERE { >> t(?status -> “Student”) . >> ?p rdf:type Person . >> ?p matric ?m >> } >> >> assigns status "Student" to every person having a matriculation >> number, >> e.g. when evaluating query Q above on database >> D := { (P1,rdf:type,Person), (P1,matric,"1111"), >> (P2,rdf:type,Person) } >> we obtain [[Q]] = {{ ?p -> P1, ?status -> "Student" }}. >> >> I think that the extension by constant patterns has several benefits >> >> - We can safely encode negation in this fragment, namely as >> A MINUS B == (A OPT (B AND t(?x->c)) FILTER (!bnd(?x)) >> - The extension is interesting from a practical perspective to >> introduce fresh constants that do not occur in the database. >> - I believe (yet did not check in detail) that this extension makes >> it quite easy to fix the proof on the expressiveness of SPARQL >> w.r.t. the issue of missing constants in SPARQL mentioned above >> >> Finally, as a side note, the extension by constant mappings gives >> us the >> expressive power to encode every first-order constraint in SPARQL >> (even >> without operator MINUS). This observation qualifies SPARQL as a >> constraint >> language and motivates extensions that can be used to enforce user- >> defined >> integrity constraints on the input database (in the style of CREATE >> ASSERTION >> statements in SQL) or to check if constraints in the database hold >> (by means >> of ASK queries, for example). However, note that we obtain this >> expressive >> power also when adding a MINUS operator to the SPARQL query language. >> Do you know if the W3C ever had in mind such constraint-extensions? >> >> Best, >> Michael -- Dr. Axel Polleres Digital Enterprise Research Institute, National University of Ireland, Galway email: axel.polleres@deri.org url: http://www.polleres.net/Received on Friday, 18 September 2009 18:08:11 GMT

*
This archive was generated by hypermail 2.2.0+W3C-0.50
: Friday, 18 September 2009 18:08:11 GMT
*