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>

CC: w3c-rdfcore-wg@w3.org

Date: Thu, 12 Jun 2003 10:40:20 +0100

Message-ID: <3EE84A84.6090900@hplb.hpl.hp.com>

To: pat hayes <phayes@ihmc.us>

CC: w3c-rdfcore-wg@w3.org

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 EDT

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