RE: Negation (Fwd: Expressive Power of SPARQL)

Another approach to negation that the WG is considering is NOT EXISTS. This pattern tests each solution of one pattern as to whether, given that pattern, another matches the graph or not..  Example:

==== Data:

@prefix  :       <http://example/> .
@prefix  rdf:    <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix  foaf:   <http://xmlns.com/foaf/0.1/> .

:alice  rdf:type   foaf:Person .
:alice  foaf:name  "Alice" .
:bob    rdf:type   foaf:Person .

==== Query:

PREFIX  rdf:    <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 
PREFIX  foaf:   <http://xmlns.com/foaf/0.1/> 

SELECT ?person
WHERE 
{
    ?person rdf:type  foaf:Person .
    NOT EXISTS { ?person foaf:name ?name }
}

==== Query Result:
?person=<http://example/bob>

- - - - - - - - - -

It's not only the empty patterns causing a MINUS pattern to evaluate to the empty result.  A constant pattern (no variables) will do the same.  MINUS removes any query solution that has no variables in common some row from the RHS of the MINUS.  MINUS can be useful as an algebra operator but if used as a graph pattern written by application writers, it can be a bit complex.

 Andy

> -----Original Message-----
> From: public-rdf-dawg-comments-request@w3.org [mailto:public-rdf-dawg-
> comments-request@w3.org] On Behalf Of Axel Polleres
> Sent: 18 September 2009 19:07
> To: public-rdf-dawg-comments@w3.org
> Subject: Negation (Fwd: Expressive Power of SPARQL)
> 
> 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, 25 September 2009 16:38:43 UTC