consider computational complexity

[VladimirAlexiev]

It would be nice for each new feature (or more realistically a bundle of features, i.e. Profile) to have some idea about its implementation and execution complexity.

Consider this scenario:

• a database of 1, 10 or 100B triples (data at rest), which are assumed valid (eg parts have been validated, parts are from a trusted valid source)
• a transaction of 1, 10 or 100M triples (data in motion)
• a shapes graph of 1 or 10k shapes. Shapes refer to both data in motion, and also data at rest.

How do you validate this scenario in a reasonable time?
That's a difficult question.

• Many implementations use in-memory models ("give me data files, give me shape files, I load them in memory and output a validation report").
  • I think all JS implementations are like this. Which is not efficient in the large-data scenario described above (@bergos , I'd love it if you prove me wrong!)
• SPARQL opens up a "door" towards "unknown" complexity. At least I'm not aware of work on assessing the practical complexity of SPARQL queries
  • If you need to run say 1M queries coming from SPARQLConstraint (part of SHACL 1.0 Core), that will ruin all efficiency
  • So much so that, a good advice is https://github.com/Sveino/Inst4CIM-KG/tree/develop/shacl-improved#use-complex-sparqltarget-but-simple-sparqlconstraint : to put the complex query in SPARQLTarget (part of SHACL 1.0 SPARQL), and only fetch output (ValidationReport) variables in SPARQLConstraint

Relevant issues:

• define sh:ReferenceShape, sh:SimpleShape to be able to limit validation effort #242 that gives an example of constant-time shape and linear-time shape.
  But I didn't define it just for the low complexity: this would be useful in a SHACL profile for Modeling.
• SHACL's Own Profiles #216 that asks for SHACL Profiles. Now I'll add "based on the complexity of features"
• Should core be unlinked from SPARQL? #235 that removed SPARQL from Core
• Structure SHACL-SHACL to match profiles #312 that asks for structuring the spec along profiles (and Structure SHACL-SHACL to match profiles #312 (comment) that comments on complexity)

[robert-david]

Besides SPARQL constraints, isn't SHACL core complexity determined if and how you use negation and/or disjunction in your shapes?
Or do you mean that we give typical usage scenarios with size of data and time estimations? Should we add performance tests to the SHACL test suite?

[afs]

This is work the community group can and should do.

The WG has responsibility to deliver on the charter.

[caribouW3]

The CG is closed, BTW. The WG can use any resource (like Use Cases, etc.) designed to support its decision making.

Should we move this to a discussion? it does not really look like a spec issue.

[VladimirAlexiev]

@robert-david Negation and Disjunction maybe add to the work in predictable ways.
But sh:node adds in unpredictable ways because it can veer off (cascade) into more and more node checks.

@caribouW3 and @afs please don't "demote" this issue. I don't think the WG should have a free hand to add any sort of new features without giving at least some thought to complexity.

Eg can I use complexity arguments to vote against order, offset, limit in expressions?

Note: this issue doesn't ask to analyze comprehensively the complexity of SHACL, but to give it some thought.

[afs]

This is work the community group can and should do.
The CG is closed, BTW.

s/group// :-)

[afs]

Eg can I use complexity arguments to vote against order, offset, limit in expressions?

Of course.

But this issue asks "for each new feature (or more realistically a bundle of features, i.e. Profile) to have some idea about its implementation and execution complexity." -- that's putting work on others, and possibly assuming implementation work done earlier in the spec process.

[TallTed]

The CG is closed, BTW.

It, or a successor CG, could be opened at any time, for CG-appropriate work to be performed in parallel to and/or after the WG. There are a number of CG+WG pairs that work in this way, such as the Credentials CG and the Verifiable Credentials WG.

Not advocating for immediate action in this direction, just food for thought.

[ashleysommer]

@VladimirAlexiev I can give some responses from the perspective of PySHACL's python shacl engine implementation.

Many implementations use in-memory models ("give me data files, give me shape files, I load them in memory and output a validation report")

Yes, this is the way PySHACL works too. It uses Python's RDFLib to create two in-memory graphs. One for the Shapes graph, and one of the Data graph. Python is not known for its speed or memory efficiency, and RDFLib is not great a handling very large in-memory graphs, so we do run into these problems you are describing.

SPARQL opens up a "door" towards "unknown" complexity.

In mid-2024 PySHACL implemented a "SPARQL-mode", where the datagraph can be given as a SPARQL endpoint target. In this mode, PySHACL does not attempt to load the datagraph into memory, instead converts all focus/value node lookups and all Core SHACL constraint to SPARQL queries and executes them against the remote graph.

There are pros and cons to running the SHACL engine in this mode. If there are many queries to execute, the overhead of HTTP calls to a remote SPARQL endpoint can hurt performance more it helps.
Secondly, most SPARQL endpoints are read-only. Even if we have SPARQL 1.1 Update endpoint, most users would not expect a SHACL validation engine to modify their remote data graph. So advanced features such as pre-validation graph inferencing, and SHACL Rules to express new triples are not supported in SPARQL-mode.

[VladimirAlexiev]

I'd be happy if:

• People give some thought to the complexity implications of various features
• Potentially, we define some modest profiles with known low complexity

I believe that there are some sweet-spot features that are both important in their own right, and low complexity.
Namely, a SHACL-for-modeling subset that doesn't include boolean operations, complex paths, complex node expressions, or complex sh:node invocations.
"The 20% of features used 80% of the time".

Coupled with some guidance or ontology concepts on how to structure shapes.
https://github.com/w3c/data-shapes/issues/242 is one such example:

• full shape (for checking all props) vs
• reference shape (for checking existence and "business type" conformance)