W3C home > Mailing lists > Public > public-rdf-wg@w3.org > May 2012

Re: RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts]

From: Pat Hayes <phayes@ihmc.us>
Date: Tue, 1 May 2012 22:40:30 -0500
Message-Id: <5D8A4269-C613-4F38-8E2E-1EDCD6717485@ihmc.us>
To: RDF Working Group <public-rdf-wg@w3.org>, RDF Working Group Issue Tracker <sysbot+tracker@w3.org>

On May 1, 2012, at 9:41 AM, RDF Working Group Issue Tracker wrote:

> RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts]
> 
> http://www.w3.org/2011/rdf-wg/track/issues/86
> 
> Raised by: Richard Cyganiak
> On product: RDF Concepts
> 
> RDF Concepts defines the term “graph equivalence”. RDF Semantics defines the term “equivalent”. I think the two definitions are not quite compatible.

Indeed, these are different concepts and the coincidence of names has given rise to confusion. 

> The RDF Concepts definition coincides with RDF Semantics *only* under simple entailment.

And that is almost an accident, in fact. 

> In more advanced forms of entailment, graphs that are not equivalent according to the RDF Concepts definition are in fact equivalent according to RDF Semantics.
> 
> The notion of equivalence defined in RDF Semantics is more general and sensible to me.
> 
> I think the best way to resolve this is to *rename* the definition in RDF Concepts, while keeping its unchanged.
> 
> The most technically correct name would perhaps be something like “simple graph equivalence”, but I note that the term “graph isomorphism” is already frequently used in the community to denote exactly the concept we're after (see e.g. Jena's Model.isIsomorphicWith() method), and is in fact a nicely descriptive term for what's actually being defined.
> 
> What do people think about:
> 
> 1. renaming “graph equivalence” to “graph isomorphism” in RDF Concepts, and
> 2. adding a sentence in the RDF Semantics section on simple entailment, stating that isomorphic graphs are equivalent under simple entailment?

+2 (That is two +1 s)

Pat

> 
> 
> This is the definition of “graph equivalence” from RDF Concepts:
> 
> [[
> Graph equivalence: Two RDF graphs G and G' are equivalent if there is a bijection M between the sets of nodes of the two graphs, such that:
> 
> 1. M maps blank nodes to blank nodes.
> 2. M(lit)=lit for all RDF literals lit which are nodes of G.
> 3. M(uri)=uri for all IRIs uri which are nodes of G.
> 4. The triple ( s, p, o ) is in G if and only if the triple ( M(s), p, M(o) ) is in G'
> 
> With this definition, M shows how each blank node in G can be replaced with a new blank node to give G'. A definition of graph equivalence is needed to support the RDF Test Cases [RDF-TESTCASES] specification.
> ]]
> http://dvcs.w3.org/hg/rdf/raw-file/default/rdf-concepts/index.html#dfn-graph-equivalence
> 
> This is the definition of “equivalent” from RDF Semantics:
> 
> [[
> Equivalent (prep., with to) True under exactly the same conditions; making identical claims about the world, when asserted. Entails and is entailed by.
> ]]
> http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#gloss
> 
> 
> 
> 

------------------------------------------------------------
IHMC                                     (850)434 8903 or (650)494 3973   
40 South Alcaniz St.           (850)202 4416   office
Pensacola                            (850)202 4440   fax
FL 32502                              (850)291 0667   mobile
phayesAT-SIGNihmc.us       http://www.ihmc.us/users/phayes
Received on Wednesday, 2 May 2012 03:41:01 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:25:48 GMT