Re: shapes-ISSUE-63 (sh:hasShape): Nested shapes: sh:hasShape function versus recursive SPARQL code generation [SHACL Spec]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 06/14/2015 10:34 PM, Holger Knublauch wrote:
> On 6/15/2015 14:12, Peter F. Patel-Schneider wrote:
>> The inner SELECT is generating bindings for ?this that are then used in
>> a MINUS construct so it should work out. At least it does in my test 
>> implementation, using Virtuoso as the SPARQL engine.
> 
> It may produce the correct results, but performance will be completely 
> inacceptable. It will start fresh iterations across all triples with
> that predicate, no matter if previous scopes and constraints have
> already eliminated most subjects. So my statement "will not work" was too
> harsh - it should have said "will not be practical". Sorry for that.

I don't think that it is evident that this approach will be any worse in
practice than a top-down one.  There are cases where this approach appears
worse, and cases where the too-down approach appears better.

>>>>> ignoring how to specify things like Xor (which together with 
>>>>> qualified cardinality restrictions may be very problematic),
>>>> I am not aware of any issue with respect to XOR and qualified 
>>>> cardinality restrictions.
>>> Your approach outlines how to map AND and OR (UNION), so how would
>>> you do Xor and QCRs?
>> One way to do XOR would be to expand s1 XOR s2 as ( s1 MINUS s2 ) OR (
>> s2 MINUS s1 )
> 
> So you evaluate all shapes twice? And for 3 operands, you evaluate
> everything 9 times?

The expansion does increase in size.  Whether the shapes are evaluated
multiple times is up to the SPARQL implementation.

>> QCRs can be done as something like FILTER EXISTS { SELECT ?this WHERE {
>> ?this <path> ?V .  FILTER EXISTS { SELECT ?this as ?V { <shape> } } } 
>> GROUP BY ?this HAVING ( COUNT (DISTINCT ?V) >= <minCardinality> ) }
> 
> Same issues - all this may work in theory, but I cannot see how this is 
> practical. Helper functions such as sh:hasShape and sh:valueCount will
> make it more efficient, easier to specify IMHO and possibly easier to
> optimize.

Again, it is not evident to me that a top-down approach is necessarily any
better.  The top-down approach can easily end up performing the same
evaluations over and over and over.

> In addition, this approach appears unable to report any useful error
> messages beside true and false. That may be OK as a substitute of
> sh:hasShape but is not viable as a general solution for the top-level
> shapes.
> 
> Holger

peter

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQEcBAEBCAAGBQJVfmeCAAoJECjN6+QThfjzctIH/inc9hxn9bzKlU9xINozyTWG
lQQ7Xxekaup7/1gHEpuWv9Z64wVYwkH+TKcWCjFu2DR7OCkPXc/CgSCddNMCZU58
AV7OVOCi+99XcER4eDH3l3ZSZR2xhci9sqBVGMDk9nfaWHGyknKm2FwXp5QkZU06
pfiax6YhbV8YYImWZYiWdc6/NvIhhYeH+LEto24h1kfpN3k0cIk/8dsYZNUA3R8L
70c/ESn507j+Or79ur0QbussmQrEknNWMt4YNFLl0VIRoJEcgYRULtXFvm3CKgPZ
4I1s9cD/OJQlA66XTxapWgaLxw/RWTPn5ntIxjaSHq3ekUbD/22b5FLNkWXZloQ=
=YLl2
-----END PGP SIGNATURE-----

Received on Monday, 15 June 2015 05:50:27 UTC