W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > June 2003

Re: blank nodes out the wazoo

From: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Date: Wed, 11 Jun 2003 07:54:02 +0100
Message-ID: <3EE6D20A.40004@hplb.hpl.hp.com>
To: pat hayes <phayes@ihmc.us>
CC: w3c-rdfcore-wg@w3.org


The problem of eliminating such blank nodes is plausibly NP complete.

Certainly GI complete, i.e. exponential.

(See related work on irredunancy of conceptual graphs
Michel Chien et Marie-Laure Mugnier, Conceptual Graphs: fundamental notions 
in Revue d'Intelligence Atificielle, Vol 5, no 4, 1992, pp 365-406.
most applicable to RDFS though)


pat hayes wrote:

> While fixing a silly mistake in the MT document, I noticed the 
> following. We require that RDF graphs contain no redundancies in the 
> sense that the same triple cannot occur more than once in the graph. 
> However, they can contain redundancies in the sense that a triple with a 
> bnode in it can be duplicated with a different bnode, even though the 
> resulting triples would look the same in a graph diagram. The resulting 
> graph has no extra information in it, but this quirk allows an RDF graph 
> to have infinitely many consequences. For example, a single triple
> a p b .
> has infinitely many consequences;
> _:x p b .
> a p _:y .
> _:z1 p _:z2 .
> _:z3 p _:z4 .
> -:z5 p _:z6 .
> ....
> where all these bnodes are distinct; see attached jpeg.
> My question is, does the WG feel that it might be worth ruling this out 
> as a syntactic possibility? If this kind of bnode-duplication were ruled 
> out, then the set of graphs simply entailed by any RDF graph would be 
> finite.  That would generalize the no-duplicate-triples condition 
> implicit in our definition of a graph as a set, to treat triples which 
> 'look' the same when you erase the bnode labels as though they literally 
> were the same.
> Pat
Received on Wednesday, 11 June 2003 02:54:17 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 20:24:23 UTC