# Re: blank nodes out the wazoo

From: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Date: Thu, 12 Jun 2003 10:40:20 +0100
Message-ID: <3EE84A84.6090900@hplb.hpl.hp.com>
To: pat hayes <phayes@ihmc.us>

```
NP

Take two directed graphs G and H

Construct an RDF Graph R as follows.

Let the nodes of R = V(G) U V(H) U { g, h, x }  (all distinct blank nodes)

Let the triples of R all have predicate rdf:value (which we will omit)

Let the triples of R be E(G) U E(H) U { <g, g'> | g' in V(G) }
U { <h, h'> | h' in V(H) } U { <x, g>, <x, h> }

then if R is irredundant we have that H is not a subgraph of G.
The directed subgraph problem is NP complete, which forms the interesting
90% of a proof of NP complexity of RDF graph irredunancy.

Your approach neglects the long distance interactions involved in blank
node structures.

Jeremy

pat hayes wrote:

>> 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
>>
>
>
```
Received on Thursday, 12 June 2003 05:40:46 UTC

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