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

Re: blank nodes out the wazoo

From: pat hayes <phayes@ihmc.us>
Date: Wed, 11 Jun 2003 16:07:54 -0500
Message-Id: <p05210612bb0d49fca5b9@[]>
To: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org

>The problem of eliminating such blank nodes is plausibly NP complete.
>Certainly GI complete, i.e. exponential.

Actually, I think its only cubic.
for each bnode B
	for each triple T containing B
		if there is a triple instantiating T, remove T

But OK< pretend I never mentioned it.


>(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.

IHMC	(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.	(850)202 4416   office
Pensacola			(850)202 4440   fax
FL 32501			(850)291 0667    cell
phayes@ihmc.us       http://www.ihmc.us/users/phayes
Received on Wednesday, 11 June 2003 17:07:58 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:54:06 UTC