W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > October 2007

Re: Issue with top-down and bottom-up semantics

From: Francis McCabe <frankmccabe@mac.com>
Date: Thu, 25 Oct 2007 22:58:26 -0700
Message-Id: <7DA24ECA-0944-450A-82D4-248A2C609A51@mac.com>
Cc: public-rdf-dawg-comments@w3.org
To: Bob MacGregor <bob.macgregor@gmail.com>

Bob:
  Thanks for your response.
  As far as open/closed world goes, I am quite aware of the benefits  
of the closed world assumption. I have been a long-time user of NaF  
myself :-)

  However, I think that SPARQL appears to be designed to 'reach out'  
to multiple knowledge bases is not your average scripting/processing  
language. For such a language the everyday assumptions behind NaF do  
not seem so valid.

  I agree that completion semantics is reasonable, for example, when  
modeling the belief store of an agent. But it is not so reasonable  
when discovering information across the Internet.

  At least the OWL community (of which I am not a member) came up  
with a modeling language that goes a long way to square the open/ 
closed impossible/pragmatic circle.

  Anyway, I think it is the combination of OPTIONAL and the flat  
model for variable quantification that creates the most damage: that  
is why evaluation is sensitive to order.
I do not think that even SQL has *that* problem as all the tables  
being queried are specified up front, with the constraints all  
separated off. (sub-queries changes that picture of course).

  If, for example, variables were locally scoped within a query, then  
you could have a more consistent semantics for OPTIONAL. (In fact,  
that is also required to give a declarative  semantics for NaF.)

Frank


On Oct 25, 2007, at 10:37 PM, Bob MacGregor wrote:

> Francis,
>
> I registered the same complaint about the lack of a declarative  
> semantics
> a few months back.  However, I don't believe that the OPTIONAL
> construct presents a problem that can't be solved.  About year and  
> a half ago,
> if I recall correctly,  a few of us worked briefly on a semantics,  
> and I believe we had
> worked out most of a declarative semantics for OPTIONAL.  It was  
> not an obvious one; I
> recall having to apply a closure axiom to the triple store to get  
> things
> to work out.  We could probably resurrect that; but there is no  
> point unless the
> committee decided to go for a declarative semantics after all.
>
> I would not agree with a suggestion to eliminate OPTIONAL from the  
> language.  It
> serves roughly the same role that NULL does in SQL, and NULL is  
> essential
> to that language.
>
> I never saw the reason for choosing an algebraic semantics in print  
> (but may
> have missed it).  It seems to be a hack to justify a particular  
> style of
> implementation, one that we have not adopted in our own triple  
> store.  Our own
> implementation of OPTIONAL definitely does not depend on the order of
> evaluation.
>
> With regard to negation as failure, I posted a challenge example a  
> while back
> that contained a double negation.  I asked whether anyone could  
> suggest
> how to implement it using OPTIONAL combined with unbound.  The silence
> was deafening, which I took to support a conjecture that in fact a  
> NAF operator (UNSAID,
> or whatever) is strictly more expressive than the current SPARQL hack.
>
> Your assumption that the Semantic Web is open world is unwarranted,  
> i.e. does
> not stand up empirically.   Assuming that information is locally  
> complete is highly
> useful more often than not.  The open world assumption does seem to  
> be widely accepted
> among academic types, and makes for a nice sound bite, but we find  
> in our
> own applications that negation-as-failure is highly useful, while  
> the open world
> assumption most of the time makes the logic less useful.  Although  
> its adoption is not
> mandatory in our implementation, we assume UNA and CWA in all of  
> the applications that I have seen.
> We also employ a variant of OWL that makes the same assumptions,  
> and is
> therefore much more useful than standard OWL.
>
> Regards,
> Bob MacGregor
> - Show quoted text -
>
>
> On 10/25/07, Francis McCabe < frankmccabe@mac.com> wrote:
> I believe that is important that SPARQL have a declarative semantics.
> This both reflects the fundamental purpose of a query language -- it
> is not a programming language -- and will make it easier to
> communicate to non-professionals the merits and benefits of using it.
>
> In the case of a query language for RDF, this is doubly the case as
> the base language is inherently declarative. (It even has a model
> theory!)
>
> It is therefore something of a disappointment to discover that SPARQL
> does not have a truly declarative semantics. It is not possibly to
> firmly state that the results of satisfying a SPARQL query are based
> on some sound inference process backed up by a model theoretic
> interpretation.
>
> I believe that the OPTIONAL feature may be one of the causes of this.
> Following a recent email conversation, I became aware that its
> semantics do not fit well with the current model for the
> quantification of variables. Certainly, the idea that a top-down
> evaluation (or a left-to-right versus left-to-right) would give
> different answers than a bottom-up evaluation is strong evidence of
> the weakness of the semantic framework.
>
> The specification hints at this, the query:
>
> PREFIX foaf: < http://xmlns.com/foaf/0.1/>
> PREFIX dc:   <http://purl.org/dc/elements/1.1/>
> SELECT ?name
>   WHERE { ?x foaf:givenName  ?name .
>           OPTIONAL { ?x dc:date ?date } .
>           FILTER (!bound(?date)) }
>
> is described as being equivalent to negation-as-failure. Giving NAF a
> declarative semantics is a non-trivial task (first done by Keith
> Clark). It involves assuming a 'completion semantics' for the
> predicates: the definitions must be interpreted as if-and-only-if;
> and furthermore, inequality of symbol must become inequality of
> denoted individuals.
>
> Both of these assumptions are antithetical to the nature of the
> semantic web which depends on the so-called Open World assumption --
> primarily because information on the SW can never be assumed to be
> complete.
>
> Although there may appear to be compelling pragmatic reasons for
> retaining the OPTIONAL feature; I believe that they are outweighed by
> the conflicts that they raise with the fundamental nature of the
> Semantic Web.
>
> Thank you for your attention
>
> Frank McCabe
>
>
>
Received on Friday, 26 October 2007 05:58:49 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:14:52 GMT