Blank nodes semantics - nominal variables? [Re: Blank nodes semantics - existential variables?]

Hi Angin, Thomas and all,

Please allow me to offer a slightly different response, drawing from a
major advance in logic from the past 20 years --- nominal quantifiers
(note the pioneers received the 2019 Alonzo Church Award, so this is
nothing obscure).

Angin said: >> I know that there has been a lot of discussion on blank
nodes in the past, cf. [1, 2, 3]. I just want to make sure that there
are no recent changes on the semantics of blank nodes that I missed.
Please let me know if I miss some recent updates in this area. Many
thanks!

Although there has been a lot of discussion on the semantics and
philosophy of blank nodes, I think this point has not received enough
attention, so can benefit from a little more thought.

I believe that the alternative semantics alluded to at times in the
other thread can be given by using nominal quantifiers for blank nodes
instead of existential quantifiers. Nominal quantifiers are more
restrictive than existential quantifiers, notably they *forbid*
"diagonalisation", which, for existential quantifiers, is the
property:

 exists x. P(x, x)  =>  exists x. exists y. P(x, y)            (diagonalisation)

By using nominal quantifiers instead of existential quantifiers, we
would allow queries such as (in a pseudo RDF query language where
blank nodes in queries are nominally quantified variables) the
following.

Nominal Query:   ASK{ :Bob :has _:b1  :Bob :has _:b2 }

The above query would fail on data below

Data:   Bob has _:b1

Note, in contrast, the standard query

Existential Query:   ASK{ :Bob :has ?x  :Bob :has ?y }

where ?x and ?y are treated existentially would succeed (see footnote
1 for more explanation).

For another differentiating example, consider the following query:

Nominal Query:   ASK{ :Bob :has _:b2  :Bob :likes _:b3 }

The above query would fail on the following data

Data:   :Bob :has _:b1  :Bob :likes _:b1

In contrast, the following query involving existential quantifiers
would succeed.

Existential query: ASK{ :Bob :has ?x  :Bob :likes ?y }

In short: if we model blank nodes using nominal quantifiers, if you
explicitly ask for two different blank nodes then you get two
different blank nodes (but you don't care what they are called).

Regarding "leaning", nominal quantifiers avoid the feature of
existential quantifiers Thomas seems to find unintuitive (if I follow
correctly Thomas!). E.g., suppose you have have a partial data set
where some resources are described in the same way (perhaps due to
harvesting data):

Dataset A:

:Bob :has _:b1
_:b1 :color :red
:Bob :has _:b2
_:b2 :color :blue
:Bob :has _:b3
_:b3 :color :red

Then the above is not equivalent (cannot be "leaned" to):

Dataset B:

:Bob :has _:b1
_:b1 :color :red
:Bob :has _:b2
_:b2 :color :blue

Thus, using Dataset A above (with three different blank nodes), for
example, we can ask whether :Bob has three things with some color.

Query:

ASK{
  :Bob :has _:b1
  _:b1 :color ?x
  :Bob :has _:b2
  _:b1 :color ?y
  :Bob :has _:b3
  _:b1 :color ?z
}

The above query would succeed on Dataset A. In contrast, the same
query would fail on Dataset B, (assuming nominal quantifiers are
used).

Historically, nominal quantifiers were invented to reason about data
that is very close to syntax, but which contains names where the name
we give to something is arbitrary, as long as it's different from
other names we give. This is probably intuitively close to how many
developers see names in RDF, so it may well be a good semantics to
choose for blank nodes (but is not the W3C standard of course).
Furthermore, they can co-exist with existential variables, e.g.,
allowing the mix of nominal data and existential queries illustrated
above.

 ...but you can probably see the fundamental problem here: the
semantics must be hidden from the user, explained by intuitive
examples, and guaranteed by tools.

Kind regards,

Ross


Footnote: Here I make quantifiers more explicit rather than using
pseudo-SPARQL syntax:

 nominal b1.( Bob has b1 )
  does *not* imply
       nominal b1. nominal b2.( :Bob :has b1  "and"   :Bob :has b2 )

 nominal b1. Bob has b1
  does imply
       exists x. exists y.( :Bob :has x  "and"   :Bob :has y )

Note that we're assuming a semantics here where
 Bob has b1
   is equivalent to
 Bob has b1  "and"   Bob has b1
.

Note, furthermore,
 nominal b1.( Bob has b1 )
   is equivalent to
 nominal b2.( Bob has b2 )
.

I emphasise: we can always rename any variable name bound by a nominal
quantier, as long as the new names don't clash with other names (this
is known as alpha-conversion), i.e., we can rename blank nodes as
expected. Thus the name of the blank nodes in the "nominal queries"
above need not be the same as those in the data in order for them to
match that given pattern, we just require that multiple names in a
query are different from each other.

Received on Tuesday, 30 June 2020 10:43:55 UTC