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, 18 September 2009 18:08:11 UTC