Re: Blank nodes semantics - nominal variables?

Hi Benjamin,

In brief, when I said semantic interpretations are not helpful I meant,
giving a semantic interpretation here on this list will not be helpful for
most members of this list. However, if you'd like a semantic interpretation
you could take [1] and restrict to closed formulas (i.e., with no free
variables) built from, RDF triples as terms where blank nodes are
variables, conjunction and nominal quantifiers, which bind variables. Also,
as you know, logic is a broad house encompassing proof theory, c.f., [2],
which can be used to achieve wonderful things without ever having a
Tarski-style semantic interpretation.

Yes, I'm sure { :Bob :has _:b2  :Bob :likes _:b3 } and { :Bob :has _:b2  }
are not equivalent under the above semantics.

Equivalence, i.e., F iff G, where F and G are formulas representing graphs,
is exactly graph isomorphism (preserving the URIs and literals assigned to
non-blank nodes, of course). The above graphs are obviously not isomorphic.
This is what makes using nominal quantifiers quite a reasonable approach to
building logics for reasoning about knowledge graphs.

Note this is just a little exercise in logic for knowledge graphs, in case
anyone thinks I'm fighting the W3C standard.

Thanks Jean for the input. Yes, probably there are no SPARQL 1.1
implementations. There are likely other knowledge graph query languages out
there that achieve this effect, since sub-graph isomorphism is an obvious
basis for a graph query language. I vaguely remember playing with an old
Haskell implementation of SPARQL (SWISH
http://www.ninebynine.org/RDFNotes/Swish/Intro.html) that was based on
subgraph isomorphism algorithms, but that was before 1.1. ...incidentally,
comparing the old 1.0 and new 1.1 RDF SPECS, I notice that the old specs
tightly match the nominal semantic described in this side thread. See the
old interpolation lemma [4] for example matches the one I stated earlier
...hmm... I missed that discussion. Probably the 1.1 editors have already
had a debate like this during the move from 1.0.

Best,

Ross


[1] AM Pitts. Nominal logic, a first order theory of names and binding.
Information and computation, 2003
https://doi.org/10.1016/S0890-5401(03)00138-X
[2] D Miller, A Tiu. A proof theory for generic judgments. ACM Transactions
on Computational Logic (TOCL), 2005
[3] https://www.w3.org/TR/rdf-mt/

P.S.: Yes. I meant ASK { :Bob :has ?x  :Bob :likes ?y } is equivalent to
ASK { :Bob :has _:b1 :Bob :has _:b2 } in SPARQL 1.1 thank you Benjamin.


On Thu, 9 Jul 2020 at 00:26, Benjamin Braatz <bb@bbraatz.eu> wrote:

> Hi Ross and all.
>
> On 05/07/2020 16:06, Ross Horne wrote:
> > Semantic interpretation are trickier to describe, typically a
> > semantics for nominal quantifiers assume we have an infinite set of
> > atomic names which we can pick from, and that meaning is invariant
> > under permutations of these names (i.e., names have no structure or
> > discernable differences).
>
> That all sounds very syntactic to me (and, somehow, just achieves the
> same that is done in RDF for blank nodes already by defining them to be
> local to the graph and requiring the standardising apart in merges etc.).
>
> Where I was trained, semantics usually meant some kind of formally
> defined models that interpret the syntax.
>
> (It really doesn't help that, e.g., in UML the syntactic things are
> called “models” and what we would have called “formal syntax” is called
> “static semantics”, there, although it's just well-formedness rules and
> really doesn't say anything about /meaning/.)
>
> > [These semantic interpretations are not usually helpful, so it can
> > be good to skip the model theory and look at the inference rules.]
>
> Why are the semantic interpretations not helpful?
>
> In my view, they come first and only then, we derive inference rules
> that are correct and complete w.r.t. the semantic interpretations.
> Without having semantic interpretations/models/whatever, inference rules
> cannot be correct and complete, but are just arbitrary.
>
> > These kinds of interpretations are a little different from what
> > you're describing, thus { :Bob :has _:b1 :Bob :has _:b2 } would not
> > be equivalent to {:Bob :has _:b3}.
>
> But they /are/ equivalent according to the RDF semantics:
> https://www.w3.org/TR/rdf11-mt/#h3_simpleentailment
>
> For every interpretation of the first one, we can just choose the
> interpretation of _:b1 or _:b2 as the intepretation of _:b3 to see that
> it is also an interpretation of the second one.
> (This should also work for nominals.)
>
> For every interpretation of the second one, we can choose the
> interpretation of _:b3 as the interpretation of _:b1 as well as _:b2 to
> see that it is also an interpretation of the first one.
> (This shouldn't, as far as I understand it, work for nominals. That's
> why I asked if nominal interpretations are required to be one-to-one in
> my first mail in this topic.)
>
> > Above, you pick up on a key distinction between nominals and
> > existentials.
> >
> > Consider data:  :Bob :has :something
> >
> > The above data would not be satisfied by the following query if
> > nominals were used.
> >
> > ASK { :Bob :has _:b3 }
>
> Still (or again), you can choose if this is an arbitrary choice only on
> the syntax or if you want to have a semantics for which this is the
> correct way of doing it.
>
> The first one is always possible. Just require that blank nodes in the
> query are only mapped (one-to-one) to blank nodes in the data and that's
> it. (…, but this would break the fact that a SPARQL query normally asks
> if the pattern in the query is entailed by the data. Here, the query
> /is/ entailed by the data, but you want the query to say no.)
>
> The second one is a little trickier. We could require that blank nodes
> are never interpreted by resources that are also the interpretation of
> an IRI or a literal. That would be a totally different semantics
> (especially together with the one-to-one requirement from above), but it
> could work, give somehow sensible results, but totally different from
> RDF as we know it.
>
> > Also, please see the example I shared with Pat to see how we might
> > allow some co-reference (via owl:sameAs) without collapsing :Bob
> > :has _:b1 :Bob :has _:b2 and :Bob :has _:b1.
>
> But this only solves the problem if we have some requirement (like a
> property being functional) that allows us to infer sameAs. Otherwise
> nominality would /require/ the blank nodes from different sources
> (different parses of the same document, different documents talking
> about the same thing, …) to behave as if they were distinct in any case.
>
> The usual (existential) RDF blank nodes are just allowed to be distinct,
> but not required to be.
>
> > Query A: ASK { :Bob :has _:b2  :Bob :likes _:b3 }
> > Query B: ASK { :Bob :has :x  :Bob :likes :y }
>
> You meant {:Bob :has ?x :Bob :likes ?y}?
>
> > The question I was getting at was more to do with the various real
> > implementations of SPARQL. Are there implementations of SPARQL that
> > are sensitive to these differences and say "no" to Query A on the
> > data :Bob :has _:b1  :Bob :likes _:b1? In other words, is there an
> > implementation of SPARQL where Query A and Query B are not
> > equivalent?
>
> That would certainly be interesting:
>
> How much do SPARQL implementations comply to the standards in this regard?
>
> Best regards,
> Benjamin
>
>