RE: Does the expressive power of SPARQL include all forms of default negation?



> -----Original Message-----
> From: public-sparql-dev-request@w3.org [mailto:public-sparql-dev-
> request@w3.org] On Behalf Of Lee Feigenbaum
> Sent: 2 September 2009 07:52
> To: Chimezie Ogbuji
> Cc: public-sparql-dev@w3.org
> Subject: Re: Does the expressive power of SPARQL include all forms of
> default negation?
> 
> Chimezie Ogbuji wrote:
> > Hello.
> >
> > I have a particular class of problems that I'm unable to formulate as a
> > SPARQL query (using the current standard).  I was hoping somebody might
> have
> > a solution and if not, perhaps this is something I can bring up for the
> WG.
> > If people think it is worth forwarding there, I can do so - I just
> wasn't
> > sure if that was the right forum initially.
> >
> > Basically, the problem is one where I want to find "all resources that
> are
> > not a member of a specific class".  This seems to be especially
> problematic
> > for RDF graphs where each resource has *multiple* rdf:type statements.
> > Consider the graph:
> >
> > _:b rdf:type D
> > _:a rdf:type C
> > _:a rdf:type D
> > _:a rdf:type B
> >
> > And we want to find "all resources that are not a member of the C
> class,"
> > where the *not* in this case is meant in the closed world sense (i.e.,
> > basically there is no statement of the form:  ?RESOURCE a C in the
> graph).
> > Otherwise, disjointness axioms can be used (i.e., disjointWith,
> > differentFrom, etc.) to entail membership with the complement of C.
> >
> > If you were to try using the MINUS ( Difference of graph patterns )
> template
> > introduced in [1] (in order to account for the fact that the simple form
> > doesn't allow you to use a vanilla OPT/FILTER/!BOUND query):
> >
> > { ?RESOURCE a ?KIND } MINUS { ?RESOURCE a C }
> >
> > You would get the following SPARQL query
> >
> > SELECT ?RESOURCE ?KIND
> > {
> >   ?RESOURCE a ?KIND
> >   OPTIONAL {
> >     ?RESOURCE a C
> >     ?RESOURCE2 a C
> >     FILTER(?RESOURCE2 = ?RESOURCE)
> >   }
> >   FILTER(!BOUND(?RESOURCE2))
> > }
>  >
> >
> > However you would get the following solution set:
> >
> > ?RESOURCE ?KIND
> > _:b       D
> > _:a       D
> > _:a       B
> 
> Hi Chime,
> 
> I actually think that your query is correct and that under SPARQL
> semantics it will return exactly the result yet you want:
> 
> ?RESOURCE ?KIND
> _:b       D
> 
> I've tested this in Glitter (Open Anzo's SPARQL engine) and I do indeed
> get only this single row. (I'd usually test this in ARQ which I have the
> most confidence in as an accurate implementation of the SPARQL
> semantics, but I can't seem to find my local copy of it right now and
> http://sparql.org is not responsive for me at the moment.)
> 
> This single solution falls out of the definition of LeftJoin and Diff in
> the current specification, I believe. If you'd like, I'd be happy to
> work through the details of the algebra.
> 
> Lee
> 
> > Which (incorrectly) includes _:a (it is a member of C).  It seems,
> perhaps
> > the source of the problem is that most of the relevant algebraic
> operations
> > (needed to express the constraint) only apply to individual solution
> sets at
> > a time (rather than a multiset of solutions as a whole).
> >
> > This makes me wonder if indeed SPARQL is as expressive as Datalog with
> > default negation (minimal, stable, stratified, or otherwise), since my
> > understanding is that the following query against the equivalent Datalog
> > program should give the correct answer.
> >
> > QUERY: not rdf_type(?RESOURCE C)
> >
> > Since it will simply check for the absence of any literal that 'matches'
> in
> > the model.
> >
> > Am I missing a simple solution to this class of problems? And if not,
> will
> > this problem carry over to the next generation of the query language?
> >
> > Thanks
> >
> > [1] Angles, R. and Gutierrez, C., "The Expressive Power of SPARQL."
> Springer

Does this do what you want? It's a bit shorter and uses a different way to get the OPTIONAL/!bound to work.

PREFIX :        <http://example/> 

SELECT ?x ?t
{
   ?x a ?t 
   OPTIONAL { ?x a ?t2 . FILTER(?t2 = :C) }
   FILTER (!bound(?t2))
}

Should work:

-------------
@prefix :        <http://example/> .
@prefix rdf:        <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix rdfs:     <http://www.w3.org/2000/01/rdf-schema#> .

:b rdf:type :D .
:a rdf:type :C .
:a rdf:type :D .
:a rdf:type :B .
-------------

Gives me:

-----------
| x  | t  |
===========
| :b | :D |
-----------


One possibility the working group is considering is NOT EXISTS (also known as UNSAID)

PREFIX :        <http://example/> 

SELECT *
{
   ?x a ?t 
   NOT EXISTS { ?x a :C }
}

-----------
| x  | t  |
===========
| :b | :D |
-----------

Which I think is easier to read.  It does not require the introduction of the artificial ?t2 although I guess many systems will optimize that case so the cost is programmer workload.

For both MINUS and NOT EXISTS, and OPTIONAL/!BOUND, we have the issue of finding everything then eliminating - maybe that's an optimizer issue.

 Andy

Received on Wednesday, 2 September 2009 09:32:28 UTC