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

Re: blank nodes out the wazoo

From: Graham Klyne <gk@ninebynine.org>
Date: Fri, 13 Jun 2003 22:10:16 +0100
Message-Id: <5.1.0.14.2.20030613220152.02392210@127.0.0.1>
To: pat hayes <phayes@ihmc.us>, Jeremy Carroll <jjc@hplb.hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org

At 14:20 13/06/03 -0500, pat hayes wrote:
>One does not need to get into the subgraph problem. The only question you 
>have to ask is, is this triple redundant? The way to find that out is to 
>see if it can be instantiated into another triple in the graph, which can 
>take at most one check per other triple. If it can, then delete it, 
>remember the instance mapping, and start again from the top. If it can't, 
>try the next triple. You can detect irredundancy in n|2 checks of one 
>triple instantiating another.

Hmmm... what am I missing?:

   ex:s1 ex:p1 _:b1        (1)
   _:b1  ex:p1 _:b2        (2)
   _:b2  ex:p1 ex:o3       (3)

So the triple (2) can be instantiated as either (1) or (3), so it's 
redundant, hence can be deleted.  But in so doing, we lose the information 
that there is a graph path:

   ex:s1 --ex:p1-> ? --ex:p1-> ? --ex:p1-> ex:o3

#g
--

BTW, Jeremy, is there an easy and efficient way to use your graph 
isomorphism algorithm to determine if G1 is isomorphic to a subgraph of G2?


-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E
Received on Friday, 13 June 2003 17:21:20 EDT

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