On Mon, Jul 2, 2012 at 3:27 AM, Dave Reynolds <dave.e.reyno...@gmail.com> wrote:
> On 02/07/12 11:07, Holger Knublauch wrote:
>>
>> On 7/2/2012 18:47, Stephen Allen wrote:
>>>
>>> On Mon, Jul 2, 2012 at 12:36 AM, Holger Knublauch
>>> <hol...@knublauch.com> wrote:
>>>>
>>>> Hi all,
>>>>
>>>> I am aware of Graph.isIsomorphicWith, but I need a function that tests
>>>> whether Graph A is a sub-set of Graph B, including the ability to map
>>>> bnodes
>>>> into each other. Does that exist in Jena?
>>>>
>>> How about:
>>>
>>> ask {
>>> graph <A> { ?s ?p ?o }
>>> minus { graph <B> { ?s ?p ?o } }
>>> }
>>
>>
>> That may work for named nodes, but what about bnode structures such as
>> complex OWL class expressions? The bnode identity may be different in
>> both graphs, yet their patterns of co-existence need to be compared. A
>> triple-by-triple comparison will not be able to handle this correctly.
>
>
> There's nothing built into Jena for this, as far as I know.
>
> It's not trivial. Subgraph isomorphism is NP-Complete whereas graph
> isomorphism (the job done by isIsomorphicWith) is (possibly) fractionally
> easier - it is NP but (probably) not NP-Complete.
>
I'm not sure this will work, but if the following assumptions hold true:
1) the only independent blank nodes only come from inference
2) both graphs use the same entailment regime
3) inferences are additive only
Then you could run the minus query on the raw triples (ie
InfGraph.getRawGraph() ). Sometimes it isn't too hard to make 1) hold
if you use consistently generated URIs instead of blanknodes in your
application.
-Stephen
