Re: bNodes as local constants

> >>> In RDF we have
> >>>
> >>> john rdf:type Person   entails   _:x rdf:type Person
> >>>
> >>> where _:x is a bNode. The entailment relationship holds because there is
> >>> an assignment for _:x which is the same as the   interpretation of the
> >>> constant john.
> >>>
> >>>
> >>> If we would translate _:x to a local constant, say, x, then this
> >>> entailment relation no longer holds:
> >>>
> >>> john rdf:type Person   not-entails   x rdf:type Person
> >>>
> >>> Although john and x may denote the same individual in some
> >>> interpretation, this is by no means the case in every interpretation
> >>> which is a model of    john rdf:type Person.
> >>>       
> >
> > Michael Kifer replies:
> >   
> >> Actually this is not a good example. A better way to approximate bnodes is
> >> to translate them into skolem in the head and into existentials in the
> >> body. This is how it is done in FLORA-2 and (I think I saw somewhere) cwm.
> >>
> >> In your example _:x rdf:type Person to the right of "entails"
> >> is a query, i.e., it is a body literal. So, it is translated into an
> >> existential and everything is hunky-dori. (Existentials in rule bodies are
> >> fine.)
> >>
> >> This is not to say that this simulation is completely adequate, but this
> >> particular case is not a problem.
> >>     
> >
> > I understood Jos to only be talking about facts (not rules) in this
> > example.   Is that also your understanding?    When you talk about
> > "entails" as if it were a rule, are you making an analogy?
> >
> > If so, then I think I agree.  Jos, your example manifests the difference
> > only when RIF Core is used to express what is entailed, and we never
> > need to to do that.  Use FOL to talk about what is entailed, and we
> > don't see a difference, do we?
> >   
> 
> the point I was trying to make in the telephone conference, and in my
> e-mail, is that the proposed translation does not work in the general
> case.  The example in my e-mail shows that.
> 
> I do acknowledge that this translation can be used for certain
> purposes.  If one wants to do entailment checking, one can always
> Skolemize existential quantifiers on the left-hand side of the
> entailment symbol.

Okay, yes, we're agreed.

> >    rif("john rdf:type f:Person")   |= exists x triple(x, rdf:type, f:Person
> )
> >    rdf("_:john rdf:type f:Person") |= exists x triple(x, rdf:type, f:Person
> )
> >
> > (Neither "john" nor "_:john" can be named in the entailments, since they
> > are both in a sense local, and so not in scope for use elsewhere.)
> >
> > You mentioned that SPARQL result sets include b-Node identifiers, but
> > those are only in-scope for a particular result set (like the x in my
> > entailments).   They are not actually revealing the local names which
> > might have been used in the data-being-queried:
> >
> >          There need not be any relation between a label _:a in the
> >          result set and a blank node in the data graph with the same
> >          label. 
> >
> >          An application writer should not expect blank node labels in a
> >          query to refer to a particular blank node in the data. 
> >
> >                 -- Current SPARQL Draft [1]
> >
> > So I don't see a problem there.  (I'm also kind of baffled on how the
> > semantics of local names in RIF are supposed to be different from the
> > semantics of file-scope existentials.  Example anyone?  I think it's the
> > same question.)
> >   
> I am not sure what you mean with that you do not see a problem there. In
> SPARQL, both the blank nodes in the RDF graph and the blank nodes in the
> result set are essentially existentially quantified variables (as the
> RDF semantics prescribes). If the blank nodes in the result set would
> not have been existentially quantified variables, but really local
> names, then the names in the result set need to correspond to the names
> in the RDF graph.

Here, I think it depends what "local name" means.   Do you have some
definition in mind, here?

> The local names in RIF are meant to be rigid identifiers, and not
> existentially quantified variables.

Yes, it sounds like you do.  So what is a local name, then?  How is it
different from both a global name (IRI, relative or not) and an
existentially quantified variable.  My intuition for local names is that
they are the same as existentially quantified variables.  If they can't
be used in communication (that is, if they are local), then I don't see
how they can be considered rigid, etc.

> There are actually very good
> reasons for that, since allowing existentially quantified variables in
> rules makes reasoning a lot harder, and often undecidable, and there are
> no know effective algorithms (as far as I am aware of).
> 
> That said, one might allow existentially quantified variables in facts
> only (selecting RDF).  In that case, as mentioned by Michael, reasoning
> can be done by Skolemizing all existentials on the left-hand side of the
> entailment symbol, and treating the right-hand side as a query, so that
> entailment might be checked through variable substitution.
> Note that, in this case, entailment checking does become more
> complicated [simple entailment in RDF; i.e. not taking into account any
> of the RDF semantics, except for blank nodes, is NP-complete in the size
> of the graphs].

Thanks for walking through this.

Maybe the local names issue is an aside.  

My suggestion for RIF, I think, is that we say that RDF b-nodes should
be Skolemized for interoperation with RIF Core.  Other RIF dialects, if
they support general existential quantification, should not require
Skolemization.   Do you think that's good enough?

     -- Sandro

Received on Wednesday, 25 April 2007 18:56:50 UTC