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

```
>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 UTC

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