W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > June 2003

Re: blank nodes out the wazoo

From: pat hayes <phayes@ihmc.us>
Date: Mon, 16 Jun 2003 16:53:41 -0500
Message-Id: <p05210601bb13e986b05b@[]>
To: Jeremy Carroll <jjc@hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org

>>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> }
>>  But not necessarily the reverse.
>(that is true ...)
>>  For example let G be
>>  <a b> <b c> <c a>
>>  and H be
>>  <d e> <e f> <d f>
>>  then the instance a=d and b=e gives a redundancy (instance which is a
>>  proper sub-RDFgraph)

OK, I see my error. Never Mind.

>irredunancy is not a local phenomenon

Quite.  Because although instantiation is transitive and so is 
subgraph, it can still be the case that an instance of a non-subgraph 
instance is a subgraph. So there is no cheap way to avoid doing a 
check of all subgraphs; which is NP.  I was under the delusion that 
one could search by backtracking down the instances, but that will 
miss some cases. Still might be room for a cleverer algorithm, but 
maybe I wont try to solve P+NP this week.

>- I need to work on my NP completeness
>proof but you've more work to do on your P proof!
>(Note to rest of group these pairs are in fact triples with a missing
>rdf:value in the middle; and all the nodes are blank - this might have
>something to do with RDF)

It means that being a lean graph is potentially a very costly 
property to check, whereas I thought it was fairly trivial. Which 
means that in general, checking non-entailment between two graphs is 
potentially expensive.

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 Monday, 16 June 2003 17:53:49 UTC

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