Re: what is LDOM? (was Re: example of recursive shapes)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Here is a nested pair of shapes:

sh:IssueShape a ldom:Shape ;
    ldom:property [
        ldom:predicate ex:reportedBy ;
        ldom:valueShape [a ldom:Shape ;
      ldom:property [
      ldom:predicate foaf:name ;
      ldom:valueType xsd:string ;
      ldom:minCount 1 ; ldom:maxCount 1 ]];
        ldom:minCount 1 ; ldom:maxCount 1
    ] .

Here is a nested pair of shapes with the "nesting" done by means of naming:

sh:IssueShape a ldom:Shape ;
    ldom:property [
        ldom:predicate ex:reportedBy ;
        ldom:valueShape sh:UserShape ;
        ldom:minCount 1 ; ldom:maxCount 1
    ] .

sh:UserShape a ldom:Shape ;
    ldom:property [
        ldom:predicate foaf:name ;
        ldom:valueType xsd:string ;
        ldom:minCount 1 ; ldom:maxCount 1
    ] ;

Here is a recursive shape (although, of course, recursion does not have to
be direct):

sh:IssueShape2 a ldom:Shape ;
    ldom:property [
        ldom:predicate ex:associatedIssue ;
        ldom:valueShape sh:IssueShape2 ;
        ldom:minCount 1 ; ldom:maxCount 10
    ] .

In the nesting cases no shape's extent depends on its own extent, so there
is no recursion.  In the last case this is not true, as the extent of
sh:IssueShape2 depends on its own extent.


Having named shapes does not imply that recursive shapes are permitted
(although if naming is allowed then recursion generally is in most modern
languages).   Recursive shapes can even be done without naming (for example
by using a graph-based syntax like RDF).



It is not completely obvious what the extent of a recursive shape should be.
My view is that the extent should be as big as possible, so in the following
RDF graph the extent of sh:IssueShape2 is the empty set:

ex:is1 ex:associatedIssue ex:is2 .
ex:is2 ex:associatedIssue ex:is1 .
ex:is1 ex:associatedIssue ex:is3 .
ex:is3 ex:associatedIssue ex:is4 .
ex:is4 ex:associatedIssue ex:is5 .

but in the following RDF graph the extent of sh:IssueShape2 is { is1, ...,
is5 }:

ex:is1 ex:associatedIssue ex:is2 .
ex:is2 ex:associatedIssue ex:is1 .
ex:is1 ex:associatedIssue ex:is3 .
ex:is3 ex:associatedIssue ex:is4 .
ex:is4 ex:associatedIssue ex:is5 .
ex:is5 ex:associatedIssue ex:is4 .


As far as I can tell, the extent of recursive shapes cannot be determined by
simply transforming the shapes into SPARQL queries, as SPARQL can't do
recursion.  As far as I know, if LDOM is indeed handling recursive shapes
then it has to be running many SPARQL queries, potentially one for each node
in the data graph.  Either that or LDOM is using an extended SPARQL engine.

- From your example below it appears that LDOM depends on an extended SPARQL
enging.   Of course, if you utilize a procedural extension to SPARQL then
you can do anything computable.


peter



On 02/09/2015 08:49 PM, Holger Knublauch wrote:
> On 1/26/2015 11:20, Peter F. Patel-Schneider wrote:
>> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
>> 
>> Indeed the wording you point out is in the document, but it does not
>> speak to the ability of LDOM to handle recursion. It simply says that
>> LDOM uses procedural recursion to handle nesting. Nesting is very
>> different from recursion.
> 
> (Peter, I am picking up this thread because you still seem unconvinced
> that LDOM can handle recursion).
> 
> Maybe my PhD in Computer Science is not sufficient to understand the 
> difference between nesting and recursion here. Do you have a definition
> of "nesting" in this context? Better: do you have an example that LDOM
> could not handle? I have added the Polentoni example to my test case
> library, and my SPARQL-based implementation returns the correct results.
> I have attached the Turtle file for your reference. The following query
> can be used to verify the two cases:
> 
> SELECT * WHERE { BIND (ldom:violatesConstraints(ex:Diego, ex:Polentoni)
> AS ?diego) . BIND (ldom:violatesConstraints(ex:Enrico, ex:Polentoni) AS
> ?enrico) . }
> 
> ex:Enrico violates constraints (?enrico is true), because he knows John
> who knows Maurizio who does not live in Northern Italy. ex:Diego does not
> violate constraints (and ?diego is false).
> 
> If you are talking about nesting, do you assume that the function 
> ldom:violatesConstraints will somehow rewrite the surrounding SPARQL
> query and then contain nested calls to itself? But this is not the case
> and would indeed not work. It is simply a SPARQL function that is
> executed like this:
> 
> Entry point: ldom:violatesConstraints(ex:Diego, ex:Polentoni) -> triggers
> the LDOM engine which looks at all constraints of ex:Polentoni including
> the ldom:all:
> 
> ex:Polentoni a          rdfs:Class ; lion:constraint  [ a
> ldom:ShapeConstraint ; ldom:all        ex:Polentoni ; ldom:predicate
> ex:knows ] ...
> 
> The LDOM engine executes all SPARQL queries attached to the constraints.
> The ldom:sparql of ldom:all is calling ldom:violatesConstraints again.
> This spawns off a new (recursive) LDOM engine, taking us back to the
> entry point.
> 
> Note that I had to add some logic to prevent endless recursion for the
> same combination of arguments of the ldom:violatesConstraints function
> within the same call stack.
> 
> Holger
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJU23PZAAoJECjN6+QThfjz2IUH/idheDs9WnJzGiaP4dF/lcpK
AiWRupKbb6UvxUsckxS7h8/Y+sl2lTRUR4nzU5nWvNQhi1LJ4XhHUGjEb8o4vkNN
yN4FBgPj3bCyTajqZeIoaiuVQzhOiUY20vsn2J1zuIfaWbTLTFk5hMazzpqhsOW1
lige5oFDcfzcY20tyI/uQz46TKSLKPPnwhZtv5XVbqCNzD3xDEmCX3BwHXc0T9Ou
a43fjrcirW+10/gx9UqfiDoQurVu4PY3jKNJ4deIJTNBxRy17vSbmrGns+2t22GB
aMvL6X66d0sLtvZonwXJxOCmHPQwGb0wY9DRrpS7PIGckIqUttaiFvBNOq0OXVA=
=QE9k
-----END PGP SIGNATURE-----

Received on Wednesday, 11 February 2015 15:23:37 UTC