Source-linked AI summary
Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer's Perspective
Lander Maes, Bryan-Elliott Tam, Jitse De Smet, Jos De Roo, Pieter Colpaert, Ruben Taelman
TL;DR
SRL provides user-defined RDF inference rules, but practitioners lack authoritative implementation guidance and the specification leaves important operations underdefined. The authors build and validate a SPARQL-based engine and a dedicated engine; Eyeleng is faster across all 25 workloads, while the approaches trade infrastructure reuse against speed and explainability.
Problem
Method
The authors build and validate two SRL engines: one reusing SPARQL infrastructure and one dedicated implementation.
Source: §1 · p. 1Results
Eyeleng is faster than Comunica on all 25 workloads, by 2.15× to 6.44×.
Source: §4.4.2 · p. 6Takeaways & Limitations
Building on Comunica provides SPARQL infrastructure, while Eyeleng runs faster by skipping the query pipeline but must implement infrastructure from scratch.
Source: §6 · p. 9SRL names query without defining its evaluation procedure and leaves provenance questions for implementers to answer.
Source: §5.1 · p. 7, §6 · p. 9
Abstract
from arXiv · showhide
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.
1. Introduction
RDF reasoning lacked a shared standard for user-defined rules, while fixed entailment regimes are rigid and computationally complex. This paper examines SRL from an implementer’s perspective by building two engines and comparing their architectural trade-offs.
1. Introduction
- Fixed RDFS and OWL entailment regimes are rigidly tied to built-in vocabularies, computationally complex, and unable to support practical tasks such as negation as failure.Earlier rule-based alternatives lacked a shared standard, fragmenting adoption into engine-specific dialects.Source: §1 · p. 1
- SRL is, to the authors’ knowledge, the first W3C-backed specification for rule-based RDF inference, though earlier reasoners existed.The specification was proposed in the W3C Data Shapes Working Group.Source: §1 · p. 1
- The paper’s implementer perspective organizes the needed building blocks as parsing, dependency analysis, stratification, and fixpoint evaluation.Source: §1 · p. 1
- The authors built a SPARQL-infrastructure-based engine by extending Comunica and Eyeleng, a dedicated JavaScript engine combining forward materialization with backward goal-directed evaluation.Both engines were validated against the SRL conformance suite and additional use-case-specific tests.Source: §1 · p. 1
- The paper compares the engines’ architectural trade-offs and examines stratification, output handling, SPARQL compatibility, and SRL’s potential for explainable reasoning.The authors also state that their insights apply broadly to SPARQL-based rule engines.Source: §1 · p. 2
2. Related work
RDF reasoning approaches span fixed entailment regimes, general rule languages, and rules embedded in SPARQL. SRL belongs to the SPARQL-based lineage while adding features for user-defined inference.
2. Related work
- Entailment regimes such as RDFS and OWL specify fixed inference over vocabularies rather than syntax for users’ custom rules.SPARQL can query under these regimes but does not thereby let users define inference rules.Source: §2 · p. 2
- Rule languages let users write implications: Datalog provides a theoretical foundation, N3 extends RDF with quoted graphs and implications, SWRL combines OWL with Horn clauses, and RIF standardizes rule interchange.The passage notes that RIF’s complexity limited adoption.Source: §2 · p. 2
- SPIN represented CONSTRUCT queries as RDF triples linked to classes, while SRL adds stratification, negation-as-failure, and stand-alone text syntax to this SPARQL-based lineage.SRL inherits SPARQL’s expression language and evaluation semantics.Source: §2 · p. 2
3. SRL
SRL rules match graph patterns and instantiate triple templates, with rule sets expressible in text or RDF syntax. Its specification defines inference operations and stratification mechanics, and the Data Shapes Working Group pursued standard-track reasoning capabilities.
3. SRL
- An SRL rule matches data with a body graph pattern and fills head triple templates from matching solutions; rule sets can import other sets and include inline data.SRL provides human-readable SRL/text and RDF-based SRL/RDF syntaxes.Source: §3 · p. 2
3.1. Foundational Concepts
- The specification defines infer and query operations, but gives an evaluation procedure only for infer.Inference iterates to a fixpoint, with conclusions immediately available to later rule firings.Source: §3.1 · pp. 2–3
- Stratification orders rule layers so negation, assignments, and blank-node creation use fully computed data from earlier strata; a closed dependency cycle makes a rule set ill-formed.Open dependencies can catch up through fixpoint iteration, whereas closed dependencies require the callee to finish first.Source: §3.1 · p. 3
- The SRL body language restricts SPARQL to triple patterns, FILTER, NOT, and SET, excluding OPTIONAL and property-path * and +.This deliberate overlap supports building an SRL engine by reusing SPARQL infrastructure.Source: §3.1 · p. 3
3.2. Why the Data Shapes Working Group Addressed Rules
- The Data Shapes Working Group’s charter included standard-track reasoning rules, dependencies, ordering, and packaging, building on the fit between SHACL graph patterns and rule bodies.The group was re-chartered in December 2024.Source: §3.2 · p. 3
4. Implementations
The paper presents two implementation architectures: one reuses SPARQL infrastructure, while the other is built from scratch. The aim is to make their pipeline building blocks reusable across algorithms.
4. Implementations
- The implementations take contrasting approaches: one reuses SPARQL infrastructure inside Comunica, while the other is built from scratch in JavaScript without an underlying SPARQL engine.Source: §4 · p. 3
- The implementation discussion focuses on the architecture and pipeline shape rather than requiring readers to follow every implementation detail.Source: §4 · p. 3
- The pipeline’s building blocks are presented so they can be reassembled using different algorithms.Source: §4 · p. 3
4.1. Comunica-based engine — pipeline and algorithms
The Comunica-based engine adds SRL parsing and forward CONSTRUCT execution to a modular SPARQL engine. It analyzes rule dependencies to order execution and reduce the work needed to identify dependent rules.
4.1. Comunica-based engine — pipeline and algorithms
- Comunica’s actor-bus architecture supports the added parse and operation actors without modifying its core.The parse actor converts SRL text into SPARQL algebra, and the operation actor runs forward-chaining CONSTRUCT operations.Source: §4.1 · p. 3
4.1.1. Pipeline
- The pipeline parses SRL into algebra, builds and stratifies a dependency graph, then executes ordered layers with CONSTRUCT operations until recursive layers reach a fixpoint.Kosaraju’s SCC algorithm and Kahn’s topological sort produce the same stratification layers as the specification’s iterative procedure.Source: §4.1.1 · pp. 3–4, Figure 1 · p. 4
4.1.2. Dependency detection
- An inverted index selects candidate rules by the most restrictive pattern position, reducing dependency detection from O(R^2) to O(R×n).For the linear-chain deep-taxonomy tests, n=1, so 100,000 rules require 100,000 rather than 10 billion pairwise checks.Source: §4.1.2 · pp. 4–5
4.2. Eyeleng — a from-scratch hybrid engine
Eyeleng is a standalone SRL engine written from scratch in JavaScript. Its hybrid strategy combines forward materialization with backward, on-demand evaluation for selected rules.
4.2. Eyeleng — a from-scratch hybrid engine
- Eyeleng implements parsing, dependency analysis, stratification, and rule execution without an underlying SPARQL engine.This gives the engine direct control over its evaluation strategy.Source: §4.2 · p. 5
- Ordinary consequences are materialized forward, while function-like computations whose assigned outputs feed other rules are evaluated backward on demand using tabling.The engine makes this choice per rule based on dependency analysis.Source: §4.2 · p. 5
- Backward evaluation keeps intermediate helper triples internal and outputs only the final inferred graph.Source: §4.2 · p. 5
4.3. Comparison
Comunica reuses SPARQL infrastructure, while Eyeleng uses a dedicated evaluator. The approaches trade inherited capabilities and infrastructure costs against speed, output handling, and proof-tree production.
4.3. Comparison
- Comunica inherits federated queries, heterogeneous input formats, browser bundling, and improvements to its underlying SPARQL engine, but its output is a flat quad stream without built-in provenance.Each rule firing also passes through the full SPARQL query pipeline.Source: §4.3 · p. 5
- Eyeleng skips the SPARQL pipeline and runs several times faster, while its backward resolution produces proof trees as a byproduct.It must implement infrastructure such as federated queries, input-format support, and browser bundling from scratch.Source: §4.3 · p. 5
- Both engines target the same specification and conformance suite, and the specification prescribes neither implementation approach.Source: §4.3 · p. 5
4.4. Performance evaluation
Across 25 workloads, Eyeleng is faster than Comunica, with speedups ranging from 2.15× to 6.44×. The evaluation measures both engines under a shared timing protocol and examines how workload characteristics shape the performance gap.
4.4.1. Setup and protocol
- Both engines were measured on the same machine and software environment.The setup used an AMD Ryzen 5 5500U, 15 GiB RAM, Linux 6.8.0, and Node.js v20.20.2.Source: §4.4.1 · p. 5
- Timing starts with the rule set in memory and ends after closure materialization, including parsing, dependency analysis, stratification, evaluation, and result materialization.Each workload ran 25 times except the six largest, which ran 5–22 times; results use medians with interquartile ranges.Source: §4.4.1 · pp. 5–6
4.4.2. Results
- 2.15×–6.44×: Eyeleng is faster than Comunica on all 25 workloads, with no crossover point.Table 1 reports median execution times and interquartile ranges.Source: §4.4.2 · p. 6, Table 1 · p. 6
- Across 10 to 100,000 rules, speedup shifts from 5.8× to 5.1×, though the deep-taxonomy suite varies rule count, data, and derivation depth together.Source: §4.4.2 · p. 6
- 193 μs per rule firing for Comunica versus 20 μs for Eyeleng yields a 9.6× difference in the firing-count suite.Both engines scale linearly as the same 6,000 matches are split across 10 to 6,000 rules; the SPARQL pipeline adds fixed cost per firing.Source: §4.4.2 · pp. 6–7
- With rule count, input, and output held constant, Comunica costs 263 μs per pattern per rule versus Eyeleng’s 50 μs, a 5.3× difference.Source: §4.4.2 · p. 7
- Both engines scale linearly with input graph size, and the gap narrows to 2.8–4.2× on data-heavy workloads versus 4–6.4× in rule-bound suites.At 100K triples, Comunica spends 79 μs per input triple and Eyeleng 24 μs.Source: §4.4.2 · p. 7
- Both engines show cubic runtime growth with recursion-chain length and a 2.15–2.78× gap, as each iteration rechecks rules against the accumulated store.The specification requires fixpoint semantics but does not prescribe the evaluation strategy; semi-naive evaluation would change the results for both engines.Source: §4.4.2 · p. 7
5. Findings
The findings distinguish a strong record for deriving triples from gaps in SRL’s query specification and a Comunica-specific blank-node syntax mismatch. They also identify proof-tree output as a path toward standardized explanations.
5. Findings
- Eyeleng passes all 166 conformance tests; Comunica passes 154, with its twelve failures confined to negative tests for malformed or nonconforming input.The authors report that Comunica derives the correct result in every test that asks it to produce triples; the remaining cases concern input rejection and validation.Source: §5 · p. 7
5.1. Explainability, Proof Trees, and the Under-defined Query Operation
- SRL names a query operation but gives it no evaluation procedure, leaving a gap in how engines should answer derivability questions.Materialization alone does not retain derivation history by default; explicit tracking can record provenance, while goal-directed querying could yield a proof tree.Source: §5.1 · pp. 7–8
- The specification should define query output—such as a proof tree, rule-to-triple bindings, or a provenance model—to make explanations interoperable.The authors note that without a specified form, implementations may provide different or no explanation mechanisms.Source: §5.1 · p. 8
5.2. Blank node syntax in WHERE clauses
- A Comunica-specific mismatch between Traqula’s blank-node patterns and Comunica’s algebra matching can make WHERE shorthand fail to match stored blank nodes.The issue arises at the component boundary, not from ambiguity in SRL; Turtle collection syntax has the same failure mode because it also expands to blank nodes.Source: §5.2 · p. 8
6. Conclusion
The conclusion finds that most SPARQL infrastructure can be reused for SRL, but the remaining gaps create important implementation trade-offs. It highlights query semantics and provenance as unresolved specification questions.
6. Conclusion
- Reusing Comunica supplies federated queries, varied input formats, browser bundling, and a SPARQL expression evaluator, while Eyeleng runs faster by skipping the SPARQL query pipeline.The paper attributes the remaining implementation challenges to areas such as explainability and output cleanliness.Source: §6 · p. 9
- The specification leaves query semantics undefined; goal-directed query with proof-tree output could standardize explainability across implementations.The conclusion also notes that the open/closed dependency distinction affects whether rules share a stratum or must be split.Source: §6 · p. 9
- SRL handles stratification, fixpoint semantics, and dependency analysis, but leaves provenance and query behavior for implementers to resolve.The conclusion frames these as open questions despite SRL’s practical foundations.Source: §6 · p. 9