Re: blank nodes out the wazoo

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