Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer's Perspective

arXiv:2609.03441 · cs.DB · Submitted 2026-09-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer's Perspective".

Jane: Here's the gist of the paper. The Shape Rules Language (SRL) Working Draft introduces user-defined production rules for deriving new RDF triples from an RDF graph using inference rules, which addresses the lack of a shared standard in rule-based reasoning systems.

Tom: RDF reasoning has traditionally relied on fixed entailment regimes such as RDFS and OWL, which are rigidly tied to built-in W3C vocabularies and suffer from high computational complexity.

Jane: Rule-based alternatives appeared early but without a shared standard, adoption fragmented into engine-specific dialects.

Tom: The proposed SRL specification in the W3C Data Shapes Working Group brings user-defined production rules into the SHACL family.

Paper summary: Tom: To recap where we are, this paper by Lander Maes and colleagues looks at the Shape Rules Language or SRL, which is a draft defining how you can use user-defined production rules to create new RDF triples from existing data.

Jane: The core thesis is that unlike fixed systems like OWL or RDFS, which have rigid rules tied to specific vocabularies, SRL gives practitioners user-defined production rules with a defined grammar and execution ordering.

Lu: The paper focuses on the fact that while they built two different implementations—one using an existing SPARQL engine and one written in JavaScript—they found key architectural trade-offs between those approaches.

Meng: They compared how fast these engines were, finding that the dedicated engine was up to six times faster than the one reusing SPARQL infrastructure for certain tasks.

Tom: The paper highlights specific concepts like stratification, which they use to prevent non-determinism in rule firing order by partitioning the rules into ordered layers or strata.

Jane: They also explored two main operations: inferring the full inference graph and querying whether a goal pattern is derivable, but only the infer operation had a defined evaluation procedure for how it runs.

Lu: One major finding they bring up is that because of this structure, you get an immediate conclusion once rules fire, which makes it easier to see the chain of reasoning happening.

Jane: This leads directly into the part about explainability, as they discuss how a top-down goal-directed query operation could naturally produce a proof tree showing exactly how the rules fired to get that result.

Tom: They also pointed out some implementation specifics, like issues with blank node syntax in WHERE clauses when comparing their algebra builder to Comunica’s path consumer.

Meng: For someone trying to deploy this at scale, those kinds of implementation details matter because they can cause unexpected breaks in the system when you try to run it on massive datasets.

Lu: Ultimately, the paper concludes that SRL has the necessary bones for a practical rule language with its stratification and fixpoint semantics handled well.

Conclusion: Jane: So, looking at this paper, "Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer's Perspective," it really hammers home that the structure of SRL is promising for creating a rule-based reasoning system.

Tom: It lays out a concrete framework for defining rules—the body and the head—and gives us these ideas about how to manage execution order through stratification, which is a big step away from those fragmented, engine-specific dialects we see today.

Lu: The implication is that if you can get the grammar and the firing order right, you're building something that doesn't just run fixed entailment but can actually derive new knowledge dynamically based on user rules.

Meng: But the paper makes it clear that this isn't a solved problem yet because they left major questions unanswered about how provenance is tracked and how to properly query the system for an explanation.

Jane: Exactly, so while the language has the scaffolding, implementers still have to figure out those crucial details about tracking where every single piece of information comes from and how to get a clear proof tree.

Tom: The authors themselves flag that these are questions implementers must answer for themselves right now regarding what provenance looks like and how query operations should work in this new language.

Lu: It’s an invitation to build, but with the understanding that you have to define the parts—like output handling and explanation mechanisms—that make it truly practical for real-world reasoning tasks.

Ghent University – imec, Belgium

cs.DB

Submitted: 2026-09-03

Updated: 2026-09-03

Journal ref: CEUR Workshop Proceedings, Vol. 4292 (2026)

Code: https://github.com/comunica/comunica-feature-shacl-rules

Project page: https://comunica.github.io/comunica-feature-shacl-rules/shacl-ui/public

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: The Shape Rules Language (SRL) Working Draft introduces user-defined production rules for deriving new RDF triples from an RDF graph using inference rules…

Key concepts

SRL
A language for creating custom rules to infer new RDF triples from existing data graphs. It uses production rules with a body (data pattern) and a head (triple templates). This aims to provide a standardized way for rule-based reasoning in RDF.
Stratification
A method used in SRL to prevent non-determinism when rules fire. Stratification orders the set of rules into distinct layers or strata, ensuring that conclusions from one layer are only visible to subsequent layers, creating an ordered sequence of inference.
Infer vs. Query
SRL defines two main operations: 'infer,' which materializes the entire graph based on rules until a fixpoint is reached, and 'query,' which checks if a specific goal pattern is derivable. The paper notes that while 'infer' has an evaluation procedure, 'query' lacks one, impacting explainability.
Provenance
The origin or history of data or triples within the reasoning process. The paper highlights that because the query operation lacks a defined evaluation procedure, bottom-up materialization in some setups does not inherently track which rules led to a specific conclusion, making provenance difficult to establish.

Terminology

Summary

The Shape Rules Language (SRL) Working Draft introduces user-defined production rules for deriving new RDF triples from an RDF graph using inference rules, which addresses the lack of a shared standard in rule-based reasoning systems. p. 0

Where the paper says it

Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer’s Perspective Lander Maes1,* , Bryan-Elliott Tam1 , Jitse De Smet1 , Jos De Roo1 , Pieter Colpaert1 and Ruben Taelman1 1Ghent University – imec, Belgium Abstract The Shape Rules Language (SRL) Working Draft defines how to derive new RDF triples from an RDF graph using inference rules.

Introduction to Reasoning Paradigms

RDF reasoning has traditionally relied on fixed entailment regimes such as RDFS and OWL, which are rigidly tied to built-in W3C vocabularies and suffer from high computational complexity. Rule-based alternatives appeared early but without a shared standard, adoption fragmented into engine-specific dialects. p. 0

Where the paper says it

While powerful for formal ontology modeling, these regimes are rigidly tied to built-in W3C vocabularies, suffer from high computational complexity [1], and operate under the Open World Assumption, which prevents practical tasks like negation as failure. Rule-based alternatives appeared early but without a shared standard, adoption fragmented into engine-specific dialects.

The proposed SRL specification in the W3C Data Shapes Working Group brings user-defined production rules into the SHACL family. p. 0
Where the paper says it

Rule-based alternatives appeared early but without a shared standard, adoption fragmented into engine-specific dialects. The proposed SRL specification in the W3C Data Shapes Working Group [2] brings user-defined production rules into the SHACL family.

SRL Core Concepts and Mechanics

SRL defines production rules consisting of a body (a graph pattern to match against the data) and a head (triple templates whose variables are filled in by matching solutions). Foundational concepts include two operations—infer (materialize the full inference graph) and query (check whether a goal pattern is derivable)—but only infer receives a defined evaluation procedure. p. 1

Where the paper says it

parent :parentOf ? Foundational Concepts The spec defines two operations—infer (materialize the full inference graph) and query (check whether a goal pattern is derivable)—but only infer receives a defined evaluation procedure.

Evaluation proceeds to a fixpoint where rules fire repeatedly until no new triples emerge, with each conclusion immediately visible to subsequent rules. p. 2
Where the paper says it

Evaluation proceeds to a fixpoint: rules fire repeatedly until no new triples emerge, with each conclusion immediately visible to subsequent rules. To prevent non-determinism—in particular, to ensure that negation-as-failure and assignment produce the same result regardless of rule execution order—the spec requires stratification.

To prevent non-determinism, the spec requires stratification, which partitions the rule set into an ordered sequence of layers (strata). p. 2
Where the paper says it

y }, the dependency becomes closed: a premature absence would cause B to draw a conclusion that the fixpoint cannot later retract, so A must fully complete before B begins. Stratification partitions the rule set into an ordered sequence of layers (strata).

Engine Architectures and Trade-offs

Two implementations were built to explore architectural trade-offs: one reuses SPARQL infrastructure inside the Comunica query engine, and another is a dedicated engine written from scratch in JavaScript. The Comunica-based engine reuses existing SPARQL infrastructure, which reduces engine-specific work but results in a moderate speed trade-off compared to a dedicated implementation. p. 0

Where the paper says it

The first reuses an existing SPARQL query engine and its query parser; the second is a dedicated engine. The SPARQL-based engine reused an existing modular parser for query construction and SPARQL CONSTRUCT for triple production, reducing engine-specific work.

Eyeleng is a dedicated engine that automatically combines forward materialization with backward goal-directed evaluation. p. 0
Where the paper says it

The first reuses SPARQL infrastructure by extending the Comunica query engine [3]. The second, Eyeleng [4], is a dedicated engine written from scratch in JavaScript that automatically combines forward materialization with backward goal-directed evaluation.

Eyeleng was two to six times faster than the Comunica-based engine, with the gap widening as rule sets grow. p. 0
Where the paper says it

The SPARQL-based engine reused an existing modular parser for query construction and SPARQL CONSTRUCT for triple production, reducing engine-specific work. The dedicated engine was two to six times faster, the gap widening as rule sets grow.

Key Lessons Learned for Implementers

The comparison of the two engines surfaces several key lessons about stratification, output handling, SPARQL compatibility, and explainability. One critical finding is that the query operation is named but never given an evaluation procedure in the spec, which matters for explainability because bottom-up materialization carries no provenance by default. p. 6

Where the paper says it

The query operation, described in §3, is named by the spec but never given an evaluation procedure. This omission matters for explainability.

A top-down, goal-directed query operation could naturally produce a proof tree showing the chain of rule firings, which is what is needed for an explanation. p. 7
Where the paper says it

bindings—but it requires explicit tracking that the spec does not mandate and that most forward-only engines skip. A top-down, goal-directed query operation would naturally produce exactly that chain.

Another implementation-specific finding concerns blank node syntax in WHERE clauses, which exposes a mismatch between how an external algebra builder produces patterns and how Comunica’s algebra path consumes them. p. 8
Where the paper says it

The open/closed distinction in the dependency graph determines whether rules share a stratum or must be split, and our Kosaraju+Kahn decomposition shows the spec’s iterative algorithm can be replaced without changing semantics. On the implementation side, blank node syntax in WHERE bodies exposes a mismatch between how an external algebra builder produces patterns and how Comunica’s algebra path consumes them—a reminder that reusing SPARQL infrastructure means inheriting its edge cases along with its strengths.

Performance Analysis and Conclusion

The performance evaluation showed that Eyeleng was faster on every one of the measured workloads, with speedups ranging from 2.15× to 6.44×. The cost per rule firing in Eyeleng is significantly lower, being about a factor of 9. p. 6

Where the paper says it

998), a factor of 5. Comunica’s per-pattern and per-firing costs are of the same order, consistent with a pipeline cost that scales with the size of the algebra tree rather than with the number of solutions it produces.

6 faster than Comunica because it avoids the full SPARQL pipeline on every firing. p. 6
Where the paper says it

the full SPARQL pipeline, parsing a CONSTRUCT, building algebra and planning execution, imposes a fixed cost per firing that a direct evaluator avoids. Because both are linear, the speedup is a ratio of two straight lines: it rises from 4.

Ultimately, the spec has the bones of a practical rule language with stratification and fixpoint semantics handled well. p. 8
Where the paper says it

On the implementation side, blank node syntax in WHERE bodies exposes a mismatch between how an external algebra builder produces patterns and how Comunica’s algebra path consumes them—a reminder that reusing SPARQL infrastructure means inheriting its edge cases along with its strengths. SRL has the bones of a practical rule language: stratification, fixpoint semantics, and dependency analysis are handled well.

However, what provenance looks like and how query works are questions implementers must answer for themselves today. p. 8
Where the paper says it

SRL has the bones of a practical rule language: stratification, fixpoint semantics, and dependency analysis are handled well. But what provenance looks like and how query works are questions implementers must answer for themselves today.

The open/closed distinction in the dependency graph determines whether rules share a stratum or must be split, and the Kosaraju+Kahn decomposition shows the spec’s iterative algorithm can be replaced without changing semantics. p. 8
Where the paper says it

The spec’s query operation is named but never defined; giving it goal-directed semantics with a proof-tree output would standardise explainability across implementations. The open/closed distinction in the dependency graph determines whether rules share a stratum or must be split, and our Kosaraju+Kahn decomposition shows the spec’s iterative algorithm can be replaced without changing semantics.

The paper concludes that SRL has the bones of a practical rule language but what provenance looks like and how query works are questions implementers must answer for themselves today. p. 8
Where the paper says it

SRL has the bones of a practical rule language: stratification, fixpoint semantics, and dependency analysis are handled well. But what provenance looks like and how query works are questions implementers must answer for themselves today.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved Explainable Reasoning through Goal-Directed Query Operation: The specification should define its query operation with a goal-directed semantics to produce a proof tree showing a step-by-step derivation showing how each goal reduces to subgoals until facts are reached, which would serve as the explanation.

  2. Enhanced Provenance Tracking in Inference: Implementations can instrument their CONSTRUCT evaluations to tag every inferred triple with rule ID, iteration, and bindings to provide a record of derivation history.

  3. Robust Input Validation in Rule Engines: The specification needs guidance on handling ill-formed rules, as the paper notes that current engines sometimes accept them instead of rejecting them. This requires defining clear criteria for input validation to ensure only well-formed rule sets are processed.

  4. Addressing Blank Node Syntax Mismatch: To prevent failure modes where Traqula assigns fixed labels to algebra patterns while Comunica treats them as identity checks, the system should replace shorthand like [ :city Paris" ] with a variable-based pattern, such as :city ?city", to ensure consistency between the parser and the engine.

  5. Flexible Evaluation Strategy: The system can support hybrid execution where it decides "per-rule: ordinary consequences are materialized forward, while predicates that act as function-like computations (rules containing assignments whose output feeds other rules) are evaluated backward, on-demand, using tabling."

Abstract

The Shape Rules Language (SRL) Working Draft defines how to derive new RDF triples from an RDF graph using inference rules. Each rule matches graph patterns and instantiates triple templates whose output feeds into validation pipelines, SPARQL queries, or further inference. RDF reasoning has traditionally relied on fixed entailment regimes (RDFS, OWL), rule-based ad-hoc languages such as N3, or other implementation-specific solutions without a shared standard. SRL introduces user-defined production rules with a defined grammar, dependency analysis, execution ordering, and termination guarantees. However, no authoritative implementation exists, leaving practitioners with little guidance on how to build a conformant engine or on what problems the language can solve. We implemented two SRL engines and evaluated both on classical RDF reasoning tasks for soundness, completeness, and speed. The first reuses an existing SPARQL query engine and its query parser; the second is a dedicated engine. The SPARQL-based engine reused an existing modular parser for query construction and SPARQL CONSTRUCT for triple production, reducing engine-specific work. The dedicated engine was two to six times faster, the gap widening as rule sets grow. Both engines were validated against the SRL conformance test suite, supplemented by additional use-case-driven tests. A usable SRL engine can be built inexpensively on top of a SPARQL engine, with a moderate speed trade-off that a dedicated implementation recovers. Despite the specification's immaturity, the language already supports practically useful reasoning tasks.

Sources

Related papers