SHACL Rules - discussion of scope and direction

[afs]

SHACL Rules

SHACL rules infer new triples. The input is a data graph and a shape graph with rules, the output is a graph of inferred triples.

Whether, and how, the output graph is added back into the data graph is a separate decision.

The design must respect both simple implementations as well as implementations focused on performance and scale.

The data graph may be large (= impractical in main memory). The shapes graph is assumed to be small enough it can be read and processed in memory.

There may be thousands of rules. (Generated mappings between datasets can easily have a large numbers of rules.)

Syntax examples are not real, nor consistent; they are just for illustration and intentionally different from reality.

SHACL Rules so far

SHACL-AF has

• Property Value Rules
• Single Triple rules
• SPARQL Rules (SPARQL CONSTRUCT)

and we now have Derived properties which use Node Expressions as generators of lists of nodes.

Targets are themselves "generators" - they are a pattern such as ?target sh:targetClass :SomeClass generating a collection of nodes.

Requirements

Please add use cases as issues, labelled with "Inferencing" and "UCR". Do not worry about overlaps or duplicates.

https://github.com/w3c/data-shapes/issues?q=is%3Aissue%20state%3Aopen%20label%3AInferencing%20label%3AUCR

• Use rules to conveniently infer a tree of triples #227
• Provide RDFS entailment #220
• Inferencing, sh:entailment, and strategies for describing entailment satisfaction #219
• reasoning: transitiveOver (transitive with "step" property) #351
• reasoning: more specialized inference constructs #353
• (how to implement SHACL Rules (forward chaining) efficiently #350 is a messed up discussion that was started before VA saw this issue... but it may still include useful insights)

Specific domains:

• Use case: The ASHRAE 223 standard (soon to be open for public review) #343
• inference: electrical CIM #355

"The latter is left to future work"

This comment in SHACL-AF is about rules depending on inferred triples from other rules. The future has arrived.

One part of this is taming CONSTRUCT-based rules.

1. CONSTRUCT-based rules can generate multiple triples and optional triples.
2. The triple patterns used to match by the rule are opaque and so a rules engine does not know how rules depends on each other
3. The pattern matching includes negation (NOT EXISTS), value negation (FILTER(?x != <uri>)) and creating new RDF terms, all of which affect evaluation when rules depend other rules.

Outline

• One language (RDF syntax, hopefully with SHACL Compact as well for easy of authoring and maintenance).
• The rules language would be neutral to the execution - backward or forward chaining, create new nodes, rule recursion, etc.
• Multiple profiles of execution. More powerful profiles may generate more triples from the same language. Profiles may restrict the syntax.
• Some profiles have well-understood evaluation properties.
• There is a "production rules" profile. A set of rules can go wrong - infinite loops, order dependent outcomes. It is more akin to programming.

Datalog¹ provides well-understood evaluation properties and there are various algorithms for execution ranging from simple-to-implement to complex. We are not starting from scratch.

Out of scope

• Truth maintenance

Note about transitivity

The rule for a transitive property is recursive. But it is a specific case of general recursive rules and might be a special case so we could have a profile that is "non-recursive + transitive properties".

The full rule:

IF (?x rdfs:subClassOf ?y) (?y rdfs:subClassOf ?z)
THEN 
   infer (?x rdfs:subClassOf ?z)

might be written:

TRANSITIVE(rdfs:subClassOf)

Footnotes

1. See, for example, part D in the book Foundations of Databases (chapters 12 to 15).
   Many university course notes and slides are online. ↩

[simonstey]

There also needs to be a clear guidance wrt. execution order of

1. individual rules across shapes:

ex:RuleShape1 #S1
	a sh:NodeShape ;
	sh:targetClass ex:Person ;
	sh:rule [ #S1R1
		a sh:SPARQLRule ;
		sh:prefixes ex: ;
		sh:order 1 ;   
		sh:construct """
			...
			"""
	] ;
	sh:rule [ #S1R2
		a sh:SPARQLRule ;
		sh:prefixes ex: ;
		sh:order 2 ;
		sh:construct """
			...
			"""
	] .
ex:RuleShape2 #S2
	a sh:NodeShape ;
	sh:targetClass ex:Person ;
	sh:rule [ #S2R1
		a sh:SPARQLRule ;
		rdfs:label "Infer uncles, i.e. male siblings of the parents of $this" ;
		sh:prefixes ex: ;
		sh:order 2 ;   
		sh:construct """
			...
			"""
	] ;
	sh:rule [ #S2R2
		a sh:SPARQLRule ;
		rdfs:label "Infer cousins, i.e. the children of the uncles" ;
		sh:prefixes ex: ;
		sh:order 4 ;
		sh:construct """
			...
			"""
	] .

• S1R1 will be executed before S1R2
• S2R1 will be executed before S2R2
• no guarantees can be made across shapes

---

2. the order in which shapes get processed

e.g. pyshacl processes NodeShapes "chronologically" (from top to bottom), whereas jena is processing them alphabetically.

[ajnelson-nist]

@simonstey - I agree with needing to specify execution order, also including when Node Expressions should be evaluated, and whether they may need to be re-evaluated. I see three executions to sequence, each of which might be able to affect one another:

• Node expressions
• Rules
• Inferencing (RDFS or OWL)

[afs]

execution order

This is part of taming CONSTRUCT-based rules.
If we can put in a substitute with RDF syntax then an engine can work out the order or do checking of declared order.

What I think is needed is a restriction to collection of triple pattern matches - NodeExpressions as filters - making new RDF terms.
BGP-FILTER-BIND in SPARQL words.

That's not to say sh:order isn't a bad thing but requiring sh:order makes managing rule sets as modules and importing them fragile/not possible.

[ajnelson-nist]

On making new RDF terms: If we're talking about the same thing around BIND, then this is where I'm concerned with foregoing a some guarantees around termination of expansion steps. For instance, I noted in Issue 311 that we should identify infinite-loop patterns as we develop node expression syntax. In fairness, CONSTRUCT and triple-rules are another spot we should be on the lookout when BIND is permitted.

[afs]

whereas jena is processing them alphabetically

That would be TopBraid SHACL?

jena-shacl does not have rules support at the moment.

[kvistgaard]

@afs

Please add use cases as issues, labelled with "Inferencing" and "UCR". Do not worry about overlaps or duplicates.

I don't have the rights to add label, but i added this use case for rules.

[robert-david]

I think having sh:order should be optional. As stated above, relying on a manually specified order can get difficult to manage. The outcomes of the validation might not be what was intended by the user, because of mistakes in the ordering, and one might not even recognise this. The default should be that the processor determines the order itself.

[ajnelson-nist]

There's a point to reconcile with SHACL 1.0's sh:order description & prescription: "sh:order is not used for validation purposes [...]." SHACL-AF laid some groundwork for Rules-oriented interpretation of sh:order.

If the point of sh:order in the context of rules is making sure some rules execute after others, then it sounds more like we're trying to set up gated progress within the context of a dependency graph. (The order-0 batch of rules executes, then the order-1 batch, etc.) Why not lean into the dependency graph angle more with sh:dependsOn, domain and range sh:Rule?

[afs]

yes - sh:order should calculable/checkable by an engine and to allow for very low cost implementations.

At scale (number of rules), and for rule set libraries, manual sh:order isn't helpful.

I can't think of a reason why one would want to override with explicit sh:order but may be there are reasons.

We need to keep it for AF SPARQL Rules.

It also plays a part IF we permit certain kinds of negation.

[afs]

work-in-progress : incomplete and inconsistent. Subject to change without warning.

• Example of RDF and compact syntax
• HTML and BNF grammars for compact syntax
• Definitions for a formal model of rules
• Define evaluation of a rule set.

https://gist.github.com/afs/2547eac679b1411acc078959ac2b3d31

[kvistgaard]

@simonstey yes, fully agree that RDF1.2 works well for this. The question is, if this is included as part of the specification, should it be restricted to RDF1.2 or also allow alternative ways to express it.

@robert-david

what would be the concrete use cases for this

The generic use case is: you find a triple in a graph. How did this statement come about? Was it created manually, like in Wikidata? Then, let's check the action log. Or was it constructed using an RML map? Then, which map on with which source data. Or was it inferred by a SHACL rule.
There are plenty of situations when it will be useful to know that. Keeping such data affects performance and storage requirements. Yet, it wouldn't affect query performance, since all provenance data can be kept in separate named graphs.

[afs]

The question is, if this is included as part of the specification, should it be restricted to RDF 1.2 or also allow alternative ways to express it.

There is work on a W3C NOTE describing an interoperability algorithm for RDF 1.1 -- draft: https://w3c.github.io/rdf-interop/spec/ .

[TallTed]

In short, use reification (<<...>>) when the statement itself is a thing you need to describe in complex ways (like its full provenance). Use annotation ({|...|}) when you just need to tack on simple metadata (like a timestamp or a confidence score).

The above is short and sweet ... but incorrect.

The following is a VERY SHORT (but I hope, accurate) paraphrasing of what's in the 20+ RDF 1.2 and SPARQL 1.2 specifications. I urge you to read the current drafts of these documents, and raise issues or PRs for anything you discover that doesn't make sense to you.

---

RDF 1.2 offers two basic improvements over RDF 1.1 (and earlier) reification, that allow you to:

1. Assert and annotate a triple without re-writing that triple. This is what the {| ... |} syntax gives you. For instance —

   ex:sub ex:pred ex:obj {| ex:claimedBy ex:Mary ;
                            ex:color     ex:Blue |}
   

   There's an invisible blank-node that identifies ("reifies") the triple ex:sub ex:pred ex:obj. The author can specify a blank-node or IRI to identify that triple with this small adjustment of the above syntax:

   ex:sub ex:pred ex:obj ~ex:identifier {| ex:claimedBy ex:Mary ;
                                           ex:color     ex:Blue |}
   

   This allows the author to make further statements about that triple by using ex:identifier instead of ex:sub ex:pred ex:obj. Also, ex:obj will be a solution of the SPARQL query, SELECT ?obj WHERE { ex:sub [?pred](ex:pred) ?obj }

2. Manually mint a "reifier" that identifies (or reifies) a triple, which is written as a tripleterm using the <<...>> syntax, à la —

   _:b rdf:reifies << ex:sub ex:pred ex:obj >> ;
       ex:claimedBy ex:Mary ;
       ex:color     ex:Blue .
   

   Such a reifier may be used as the object or subject of other triples. However, a tripleterm, similar to a literal, may only be used as an object.

   The key feature of this structure is that the tripleterm is not asserted in the graph, so ex:obj will not be a solution of the SPARQL query, SELECT ?obj WHERE { ex:sub ex:pred ?obj }.

(@afs — Please review the above and flag anything I mis-stated.)

[afs]

As @simonstey says "Annotation is syntactic sugar".

RDF 1.2 offers two basic improvements

Annotation syntax is not part of the RDF 1.2 data model. It is in some concrete syntaxes.

In short, use reification (<<...>>) ...

For a summary or advice when writing provenance metadata, I think that text captures the spirit.

This is a discussion about "SHACL Rules".

[afs]

The same way, as there is a Validation Report Vocabulary

As a general concept, having a provenance report is interesting - which processes were applied and where did the inputs come from.

That is not the same as detailed exactly why a process made a decision - that's more related to trust maintenance and also while the overall inferred triples don't changes, the choice of algorithm might change the cause, or even running twice (same data, same rules) may change (e.g. parallel rules processing - rules is very amenable to parallel processing.

I think truth maintenance is out of scope through, if nothing else on time scale grounds - we can declare success without it.

Now, if a group of people want to propose an Inference Vocabulary for the provenance of the graph of inferred triples (with allowance for each inferred triple as an optional extra), a Working Group NOTE could be the way to go. A NOTE does not need to be named in the charter. It can be evolving - while recommendations become published and immutable, notes are not. This gives the work a chance to evolve on a separate timeline to the rules spec.