W3C home > Mailing lists > Public > semantic-web@w3.org > March 2011

FW: Blank nodes, "leaning", and the LEM

From: <tim.glover@bt.com>
Date: Wed, 23 Mar 2011 12:41:51 +0000
To: <semantic-web@w3.org>
Message-ID: <ABEDE2E0F379C44F9A8A046505B360CF4CAF9A7A8E@EMV63-UKRD.domain1.systemhost.net>


From: Glover,T,Tim,DES5 R
Sent: 23 March 2011 12:38
To: 'Gregg Reynolds'
Subject: RE: Blank nodes, "leaning", and the LEM


Greg,

As  you pointed out in your previous email, any resemblance of RDF  to predicate logic is coincidental, accidental and entirely misleading. Blank nodes are analogous to existential variables in PL, but the systems are completely  different.

The only way is to understand RDF is by reference to Pat Hayes’ semantics of 2004, which is the definitive description of RDF. This document makes explicit many of the “heresies” you mentioned earlier.

According to this document,


An RDF graph  is a set of RDF triples.

A sub-graph of an RDF graph is a subset of the triples in the graph

A proper instance of a graph is an instance in which a blank node has been replaced by a name, or two blank nodes in the graph have been mapped into the same node in the instance.

An RDF graph is lean if it has no instance which is a proper sub-graph of the graph. For example, the graph

<ex:a> <ex:p> _:x .
_:y <ex:p> _:x .

is not lean<http://www.w3.org/TR/rdf-mt/#deflean>, but

<ex:a> <ex:p> _:x .
_:x <ex:p> _:x .

is lean<http://www.w3.org/TR/rdf-mt/#deflean>.

The first example is not lean, because it has the instance <ex:a> <ex:p> _:x , obtained by mapping _:y to <ex:a>. The second example is lean because there is no mapping of _:x to anything which is a proper sub-graph of the original.

Taking your example,


[1]  <ex:Pedro ex:owns _:x>,  <ex:Pedro ex:owns _:y>

[2] <ex:Pedro ex:owns _:x>


[1] is not lean because it has the proper instance <ex:Pedro ex:owns _:x>,<ex:Pedro ex:owns _:x>, obtained by substituting _:x for _:y.

You go on to say

Informally, leaning is premised on the idea that both clauses in [1] "say the same thing", namely that Pedro owns something.  So one of the clauses can be removed

No, leaning is premised on the idea of a syntactic  substitution of blank nodes for something else.

I don't think this works logically.

Well it works logically, but the logic is very different from predicate logic. RDF is not predicate logic!! I strongly recommend reading the semantics document in full, and spending time on it.

BTW, do not make the common mistake that the triple <a b c> represents the graph   a---b--->c.  An RDF “graph” is actually a hyper-graph in which the triples are edges, each linking three nodes.   This can’t be drawn easily -  Its best just to use the definition “an rdf graph is a set of triples” and leave it at that

Best wishes,

Tim


From: semantic-web-request@w3.org [mailto:semantic-web-request@w3.org] On Behalf Of Gregg Reynolds
Sent: 23 March 2011 11:40
To: SW-forum Web
Subject: Blank nodes, "leaning", and the LEM

I think the definition of leaning might be a little problematic so I could use a reality check.

RDF Semantics defines (sort of) blank nodes as existentially quantified variables.  Ok.

If I understand "leaning" correctly  (aside: something wrong with "normalization"?) it works something like the following.  Graph [1] below is not lean; graph [2] is the "lean" version of graph [1]:

[1]  <ex:Pedro ex:owns _:x>,  <ex:Pedro ex:owns _:y>

[2] <ex:Pedro ex:owns _:x>

Informally, leaning is premised on the idea that both clauses in [1] "say the same thing", namely that Pedro owns something.  So one of the clauses can be removed.  (BTW, the example is inspired by the famous 'donkey sentence' "Every farmer who owns a donkey beats it".)

I don't think this works logically.  Treating the blank nodes as existentially quantified variables and translating into logic (using email markup from Z, where %E% means "There exists"), [3] is equivalent to [1]:

[3]   %E% x, y @ Owns(Pedro, x) /\ Owns(Pedro y)

Leaning substitutes x for y in [3].  (Alternatively: it substitutes z for both) and then removes the redundant clause.  But doesn't that violate the rules of substitution?  Both x and y are bound in [3]; substituting x for y or z for both changes the meaning of [3].

The problem I see is that even if the clauses in [1] individually mean "Pedro owns something", reading them as redundant means that conjunction must be vacuous.  But I don't see how that can be right; logical /\ is meaningful.  So the clauses in [1] should be read "Pedro owns some x" and "Pedro owns some y"; substituting "some thing" for both changes the meaning.  It amounts to an unmotivated abstraction.

To put it another way, the symbols 'x' and 'y' in [1] are not purely extensional.  Being distinct (bound) symbols, they have different intensions and are not interchangeable.

That's the syntactic view, but the semantic view is equally problematic.  The problem is that existentially quantified  sentences  characterize populations, not individuals; so existentially quantified variables do not denote individuals.  Sentence [2] says that *some* individual in the population under consideration is owned by Pedro; it does not say that _:x denotes such an individual.  So [1] could characterize a population containing one thing that Pedro owns, or it could characterize a population containing two or more such individuals:  either _:x = _:y or _:x != _:y. We have no way of knowing which.    The Law of the Excluded Middle rears its ugly head.

If [1] were a *description* of a population we could survey it and decide which case holds; but I don't see how RDF can be treated as anything but a constructive language, meaning that [1] must be treated not as description but as prescription.  The problem then is that we don't know which population to construct.  Unless we outlaw the LEM, in which case  we construct a population with exactly two individuals owned by Pedro, and leaning is invalid.  At least I think that's how it would work.  My understanding is that outlawing the LEM would require choosing _:x != _:y in [3], but I'm not entirely confident that this is correct.  I guess it relies on the implicit assumption that  P != Q in P /\ Q.  Certainly one cannot *infer* P = Q from the conjunction.  Maybe the real problem is that data description languages and logical calculi are just different beasts.

To put it yet another way, leaning seems to rely on the truth value of the clauses in [1] rather than their meanings.  But by that reasoning we could discard all true clauses except one in any conjunction.  Truth would be preserved, but meaning would be mangled.

Leaning amounts to the selection of _:x = _:y over _:x != _:y.  I guess you could consider that one way of dealing with the LEM, but if I'm not mistaken it amounts to a redefinition of logical conjunction, which seems a little dubious.  Or maybe not; but it sure seems counter-intuitive.  It also seems incompatible with open-world semantics, which embraces "we don't know".

Does that make sense?  Am I missing something?

Thanks,

Gregg
Received on Wednesday, 23 March 2011 12:42:28 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:42:26 UTC