Re: blank nodes out the wazoo

NO

The problem of eliminating such blank nodes is plausibly NP complete.

Certainly GI complete, i.e. exponential.

(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 Wednesday, 11 June 2003 02:54:17 UTC