# Re: blank nodes out the wazoo

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

```
>Jeremy:
>>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> }
>
>
>Pat:
>>  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.

Pat
--
---------------------------------------------------------------------
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