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@[10.0.100.24]>
To: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org

>NO
>
>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
	loop
loop

But OK< pretend I never mentioned it.

Pat


>(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)
>
>Jeremy
>
>
>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


-- 
---------------------------------------------------------------------
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 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:57:55 EDT