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

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

From: Bob MacGregor <bob.macgregor@gmail.com>
Date: Thu, 25 Oct 2007 22:37:05 -0700
Message-ID: <a0d0f8f70710252237r7dab2c76mec09da1f2a83e72d@mail.gmail.com>
To: "Francis McCabe" <frankmccabe@mac.com>
Cc: public-rdf-dawg-comments@w3.org
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 Saturday, 27 October 2007 20:26:57 GMT

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