Re: Comparing shapes

On 2022-03-05 7:21 pm, Florian Kleedorfer wrote:
> Hello,
>
> I am looking for a way to compare shapes in terms of their sets of 
> valid nodes.
>
> For nodes A and B in an RDF graph, I have sets S(A) and S(B) of shapes 
> that target A or B, respectively. I am interested in the relationship 
> of the sets V(S(A)) and V(S(B)) of valid nodes according to those 
> shapes, *without looking at data*. I would like to know: do the sets 
> of valid nodes overlap, is one contained in the other, or are they 
> disjunct. Is there an algorithm that allows me to calculate that?
I am not aware of such an algorithm but it sounds like an interesting 
research question. I guess it relates to (OWL) class subsumption, but 
without DL foundation.
>
> I don't think there is, so as a pragmatic (and not very interesting) 
> proxy for this functionality, I'll compare S(A) and S(B) element-wise 
> (i.e. shape by shape), for equivalence, which allows for calculating 
> the set relationships I am interested in. If all shapes in S(A) have 
> an equivalent shape in S(B) and vice versa, the sets are identical, if 
> there are extra shapes in one of them, it is contained in the other, 
> if there are extra shapes in both, they overlap, if there are no 
> equivalent ones, they are disjunct. For this, however, I need a way to 
> compare shapes for equality.
Wouldn't this only cover the equality cases, but what about sub-sets. 
For example a shape A with sh:minCount 1 is more general than shape B 
with sh:minCount 2 (for the same property), so |V(S(A))| > |V(S(B))|. I 
guess for that algorithm you'd need to compare each pair of constraints 
using background knowledge on how to compare individual constraint 
parameters. The question of sub-shapes sounds more interesting to me 
than pure equivalence.
> My idea for the comparison would be to check if the subgraphs 
> reachable via predicates from the SHACL vocabulary, starting from the 
> shapes' main nodes are isomorphic. Is there a better way to check for 
> equivalence? Is there a reason why this whole approach might not work?

As long as your isomorphism would use a mapping table (so that ex1:Shape 
would be substituted with ex2:Shape everywhere) this could work.

Holger

Received on Sunday, 6 March 2022 22:53:36 UTC