ISSUE-86: Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics

GraphIsomorphism

Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics

State:

CLOSED

Product:

RDF Concepts

Raised by:

Richard Cyganiak

Opened on:

2012-05-01

Description:

RDF Concepts defines the term “graph equivalence”. RDF Semantics defines the term “equivalent”. I think the two definitions are not quite compatible. The RDF Concepts definition coincides with RDF Semantics *only* under simple entailment. 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?


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

Related Actions Items:

No related actions

Related emails:

1. Re: RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts] (from phayes@ihmc.us on 2012-05-01)
2. Re: RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts] (from david@3roundstones.com on 2012-05-01)
3. RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts] (from sysbot+tracker@w3.org on 2012-05-01)

Related notes:

Display change log