This section describes the status of this
document at the time of its publication. A list of current W3C
publications and the latest revision of this technical report can be found
in the
W3C standards and drafts index.
Publication as
a Working Draft does not imply endorsement
by W3C and its Members.
This is a draft document and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to cite this document as other
than a work in progress.
Future updates to this upcoming recommendation may incorporate
new features.
This document was produced by a group
operating under the
W3C Patent
Policy.
W3C maintains a
public list of any patent disclosures
made in connection with the deliverables of
the group; that page also includes
instructions for disclosing a patent. An individual who has actual
knowledge of a patent that the individual believes contains
Essential Claim(s)
must disclose the information in accordance with
section 6 of the W3C Patent Policy.
This document introduces SPARQL-RL. It is a mechanism for
deriving new RDF triples from existing RDF data through declarative rules.
The document defines the syntax and semantics of rule-based inference.
Implementations of SPARQL-RL provide one or both of the operations
infer and query.
The infer operation applies the rules to a given
base graph and produces an inference graph containing the
RDF triples derived by rule evaluation that do not appear in the base graph.
Combining the inference graph with the base graph is optional and
left to users.
The query operation determines whether and how a
given goal pattern can be derived from the base graph
using the rules.
SPARQL-RL allows the creation of new RDF terms, including blank nodes,
that can be used in triple templates in the head of rules.
SPARQL-RL also supports negation as failure, which could lead to
different inference graphs depending on the order in which rules are
evaluated. To avoid this, rules are evaluated using the technique
of stratification, which establishes an ordering among rules,
ensuring that the same inference graph is always produced.
SPARQL-RL can be referred to as SRL when the context is clear.
1.1 Terminology
The following specifications provide fundamental terminology
used in this document:
Within this document, the following namespace prefix bindings are used:
Prefix
Namespace
rdf:
http://www.w3.org/1999/02/22-rdf-syntax-ns#
xsd:
http://www.w3.org/2001/XMLSchema#
:
http://example/
Throughout the document, color-coded boxes contain rules in SPARQL-RL syntax
or contain RDF graphs in Turtle syntax.
# This box represents rules
# This box represents input data
# This box represents inferred data
2. Conformance
As well as sections marked as non-normative, all authoring guidelines, diagrams, examples, and notes in this specification are non-normative. Everything else in this specification is normative.
The key words MAY, MUST, MUST NOT, and SHOULD in this document
are to be interpreted as described in
BCP 14
[RFC2119] [RFC8174]
when, and only when, they appear in all
capitals, as shown here.
This specification defines conformance criteria for:
SPARQL-RL infers new triples given a base graph and a rule set.
The output of evaluation is an inference graph containing the derived
triples that do not appear in the base graph.
Each rule has a pattern, called the body, and a result
template, called the head.
A rule is executed by finding the values for variables in the body
so that the body matches the combined base graph and
any inferred triples from the execution up to this point.
These values are then used to instantiate the triple templates
in the rule head to produce new inferred triples.
The rules are executed until no more triples are inferred,
and rules may be executed more than once as new inferred triples
become available.
SPARQL-RL execution is defined so that the order of rule execution
does not lead to different outcomes when creating new RDF terms,
including new blank nodes, or when testing for the absence of a
pattern. In other words, the same inference graph is produced
regardless of the order of rule execution.
SPARQL-RL has a human-friendly syntax inspired by SPARQL 1.2 Query Language.
Rule set evaluation contains elements similar to SPARQL, with differences
in the details to ensure that the same inference graph is produced
regardless of the order of rule execution.
The examples in this section describe software components and
their dependencies: a frontend calls an application server, and
the application server queries a database that has a known
vulnerability.
3.1 Triple Patterns
A triple pattern is matched against triple data to give
values to variables. The pattern has
three elements, each of which is an RDF term, a variable,
or is a pattern for a triple term containing variables.
In this first example, we have the following data in the base graph and rule set:
The above rules, applied to the data, will conclude that
:frontend depends on :app, and that :app depends on
:db, whatever the kind of dependency.
We can then derive :exposedTo relationships by adding a rule that depends
on :dependsOn triples produced by the other rules
(see also 4.3 Rule Dependency) below:
3.2 Recursion
The :exposedTo rule of the previous section only reaches direct
dependencies: :frontend does not depend directly on :db, so
no :exposedTo triple is inferred for :frontend.
To propagate exposure along dependency chains of any length, we
replace that rule with two rules: a component is exposed to a
vulnerability it has, and a component is exposed to any
vulnerability that its direct dependencies are exposed to:
Compared with the previous example, this adds
:db :exposedTo :vuln1 — the database is exposed to its
own vulnerability — and :frontend :exposedTo :vuln1:
the exposure reaches :frontend through the chain of
dependencies, however long the chain.
This last rule is a recursive rule: the body of the rule
depends on the head of the rule.
3.3 Filtering
We can use expressions in the body of rules to restrict the values of variables
in the matching of the body.
For example, given the severity of each vulnerability,
we can give a status to components that are exposed to a severe
vulnerability:
FILTER evaluates an expression and keeps the current
set of variable bindings if the expression evaluates to true, and it discards the
current set of variable bindings if the expression evaluates to false.
This is the same as the
FILTER operation of SPARQL
and SPARQL-RL provides many of the same functions and operators as SPARQL.
3.4 Negation
Negation is used to specify a pattern that must not match.
This is called "negation as failure".
In order to evaluate a negation element, the rule set evaluation algorithm
ensures that all the rules that could produce triples matching the pattern
in the negation element have been completed. This is called
stratification and ensures that the negation is based
on all the relevant possible triples, whether from the data or
from other rules. The rule containing the negation is
said to depend on the rules generating these triples
(see 4.3 Rule Dependency below).
3.5 Assignment and Creating RDF Terms
Assignment allows a rule to assign the result of an expression to a variable
in the body of a rule. This can be used to create new RDF terms based
on the data.
Blank nodes can be used in the rule head, and each generates a fresh blank node
each time rule evaluation generates triples.
Rules involving assignments, rules that create blank nodes
from evaluation of the rule head and rules with a template
that involves a triple term containing variables
are run-once rules.
Such rules are run after all the rules that could produce data that they depend on,
and before any rules that depend on the data they produce.
This condition ensures that such rules do not loop back to themselves
and cause the creation of an unbounded number of RDF terms.
Note
A constant RDF term in a rule head does not make a rule a
run-once rule, even when the term does not occur in the
base graph: the rule contributes the same term each time it is
evaluated, so it can only add a bounded number of terms.
If evaluating the expression in an assignment causes an error,
then the current solution mapping is rejected by the assignment.
3.6 Importing Rule Sets
A SPARQL-RL rule set can incorporate other rule sets by
including their URLs in the rule set imports of the rule set.
This allows rules to be structured into libraries shared between rule sets.
The IMPORTS statements of a rule set are processed before any of the rules
in the rule set are evaluated. During the importing step, if an imported rule set
has its own imports, those are also processed recursively.
Traversing IMPORTS statements during the processing of rule sets may
encounter cyclic imports. A rule set is imported only once;
cycles in the import statements graph do not lead to infinite loops.
Data blocks provide RDF triples directly to the rule set evaluation.
Triples in data blocks are added to the inference graph and are available for
matching in the body of rules.
For example, a rule set can ship with known facts asserted
directly, rather than derived from data:
Note
A data block is equivalent to a rule with an empty body:
its triples are part of the inference graph without any rule
being evaluated.
3.8 Matching Base Data
During rule set evaluation it may be
necessary to pattern match only on the original base graph,
not on any inferred triples.
An example of this is setting a default value.
The rule must test whether the base graph already contains a value and, if not,
the rule can then calculate a default value.
Using NOT DATA allows other parts of the rule body to match inferred triples.
It is also possible to perform all rule body matching against the base graph by
using WHERE DATA.
Such rules then only rely on matching from the base graph.
Rules are organized into rule sets.
A rule set and a data graph (the base graph) are inputs to evaluation.
The output is a graph, called the inference graph,
which is the set of triples produced by the evaluation process
that do not appear in the base graph.
During evaluation, triples inferred based on one rule are
available for matching in other rules.
Rule set evaluation proceeds until
no further triples can be inferred
from the inputs of the rule set and the base graph.
Evaluation starts with steps to
prepare a rule set
before the rules themselves are evaluated:
Where supported, the imports of the input rule set are resolved to form a
rule set that includes all the rules of all
imported rule sets.
A processor signals an error if any import is not acceptable
to the processor (4.5 Processing Imports).
Once a rule set has been prepared, evaluation proceeds
by taking each layer from the stratification, in order,
evaluating the rules in that layer to completion,
and then moving on to the next layer.
When triples are inferred by execution of a rule, they are immediately
available to other rules as those rules are executed.
4. SPARQL-RL Abstract Syntax
The SPARQL-RL Abstract Syntax is the logical structure of SPARQL-RL.
It is used to define the execution algorithm of SPARQL-RL.
Rule set imports (often just "imports") are
the collection of URLs
from the IMPORTS statements
for other rule sets that will be included during evaluation.
Rule
A rule contains a rule head (often just "head"),
a rule body (often just "body"),
and a flag.evaldata
to indicate which
graph to use for matching triple patterns in the body.
A rule can be given a URI or a blank node to help identify it.
Run-once rule
A run-once rule is a rule that is run exactly once at a
particular point in the evaluation of a rule set.
A rule is a run-once rule if any of the following hold:
Query has the effect of performing an infer operation,
followed by matching the goal pattern to the combined
base graph and inference graph.
The query operation may not evaluate all rules; instead, it
may only evaluate rules that are necessary to answer the query
goal.
SPARQL-RL processor
A SPARQL-RL processor is a system that implements the SPARQL-RL
specification, can evaluate rule sets, and provides one or both
of the operations infer and query.
In a triple pattern or a triple template,
position 1 of the tuple is informally called the subject,
position 2 is informally called the predicate, and
position 3 is informally called the object.
Note
The elements of a sequence of rule elements are labeled starting at 1.
The following notation is used for the various components of rule sets and rules.
A boolean flag; if false, the negation.inner is matched
against the base graph.
4.2 Well-formedness Conditions
Well-formedness is a set of conditions on the abstract syntax of
a rule set. Together, these conditions ensure
that a variable in the
head of a rule has a value defined in the body of the rule;
that each variable in a filter element
or assignment expression
has a value at the point of evaluation;
and that each
assignment variable
in a rule is new and has not been used earlier in the rule body.
Let elti be the i-th element of a sequence of
rule elements, and let N be the length of the sequence.
Let V0 be the initial variables of the sequence.
Let Vi, for i
from 1 to N
be the set of variables in-scope after element
elti.
A rule set is a well-formed rule set if and only if all
rules of the rule set are well-formed rules.
4.3 Rule Dependency
A rule R1 depends on a rule R2 if the output of the second rule
affects the evaluation of the body of the first rule. That is, the head of R2
has a triple template that can generate a triple that matches
a triple pattern in the body of R1,
either as a triple pattern element or inside a negation element.
There are two kinds of dependency:
closed dependencies and open dependencies.
A closed dependency ensures that rule R2
has generated all its possible output before rule R1 is executed.
If a rule dependency is not closed, it is an open dependency.
It allows the first rule R1 to be executed
while the rule R2 might be run again to generate further triples
which can then cause R1 to be reevaluated with the new triples from R2.
A rule with flag .evaldata set to false matches using the
base graph and the rule has no dependencies.
In this first example, the first rule has an open dependency
on the second rule.
In this second example, the first rule has a closed dependency
on the second rule: the triple pattern ?x :status :criticallyExposed
occurs inside a negation element of the first rule and
matches the triple template in the head of the second rule.
The first rule cannot be evaluated until the second rule
has generated all its possible output.
A triple template can generate an
RDF tripleT1
if there are values for the variables of the
triple template such that replacing variables by values
in the template gives a triple T2 where
T2equalsT1.
Similarly, a triple pattern matches a triple T1
if there are values for the variables of the
triple pattern such that replacing variables, including
treating blank nodes as variables,
in the pattern by the values gives a triple T2 where
T2equalsT1.
If a variable is used more than once in a triple template
or triple pattern, then the same RDF term
is used as the replacement.
Replacing variables by RDF terms in a triple pattern
includes replacing variables inside triple terms.
4.3.1 Dependency Graph
The dependencies between rules are represented as a directed graph,
called the dependency graph.
The vertices of the graph are the rules of the rule set, and the edges
are labeled either open or closed according to
whether the dependency is an open dependency or a closed dependency.
Dependency graph
A dependency graph of a rule set is a directed graph where each
vertex is a rule in the rule set, and an edge exists from rule R1
to rule R2 if R1 depends on R2.
The edge is labeled either open
or closed according to whether the dependency
is an open dependency or a closed dependency.
The dependency graph is not affected by the base graph.
4.3.2 Dependency Graph Algorithm
The following algorithm gives one
possible method for constructing the dependency graph from a
rule set. Conformance depends on producing a dependency graph
that meets the definitions of a dependency graph,
not on the use of this procedure.
define mergeLabel(oldLabel, newLabel):
# Closed dependency overrides open dependency.
if oldLabel == "open" and newLabel == "open":
the result is "open"
else:
the result is "closed"
endif
enddefine
# output -- Dependency graph with rule vertices and labeled edges.
define buildDependencyGraph(ruleSet):
# edgeLabelMap maps (R1, R2) to "open" or "closed"
let edgeLabelMap be a map from pair (rule, rule) to label
foreach rule R1 in ruleSet.rules:
let bodyDependencies = {}
if R1.evaldata then:
# Classify each triple pattern TP in the rule as requiring "open" or "closed"
# depending on whether it is in a negation element or not.
foreach rule element RBE in R1.body:
if RBE is a negation element:
if RBE.evaldata then:
foreach triple pattern TP in RBE.inner:
let item be a pair (TP, "closed")
add item to bodyDependencies
endfor
endif
else if RBE is a triple pattern element of triple pattern TP:
let item be a pair (TP, "open")
add item to bodyDependencies
else if RBE is a filter element:
# Do nothing
else if RBE is an assignment element:
# Do nothing
endif
endfor
endif
foreach pair (triple pattern TP, depLabel) in bodyDependencies:
if R1 is a run-once rule:
set depLabel to "closed"
endif
# Find dependencies for this triple pattern element or negation element.
foreach rule R2 in ruleSet.rules:
foreach triple template TT in R2.head:
if triple pattern TP matches triple template TT:
let key = (R1, R2)
if edgeLabelMap contains key:
let oldLabel = edgeLabelMap.get(key)
let merged = mergeLabel(oldLabel, depLabel)
edgeLabelMap.set(key, merged)
else:
edgeLabelMap.set(key, depLabel)
endif
endif
endfor
endfor
endfor
endfor
let DP = { }
foreach entry ((R1, R2), label) in edgeLabelMap:
add an edge (R1 -> R2) labeled with label to DP
endfor
the result is DP
enddefine
A stratification process may also be used to make other evaluation
decisions. This document describes the necessary conditions for
consistent evaluation and gives one possible way to form a
stratification. Implementations need to meet the conditions
described here in order to get compatible behavior, but they are not
required to implement the algorithm as presented.
Stratification layer
A stratification layerSL is a pair of disjoint sets of
rules (SL.once, SL.general).
SL.once is exactly the run-once rules of the layer;
these rules are each evaluated
exactly once at the start of evaluation of the stratification layer.
SL.general is the set of remaining rules of the layer,
which are evaluated repeatedly until no new triples are inferred.
Stratification is only defined when the following condition is
satisfied. If a rule set does not meet this condition, then this
specification does not define an outcome for the evaluation of
such a rule set.
The following algorithm gives one possible stratification based solely
on the rule set.
define stratification(ruleSet):
let DP = Dependency graph for the rule set.
let stratumMap be a map from rule to integer
# The dependency graph should satisfy the stratification condition.
# The check for unbounded stratification is a guard
# due to a violation of the stratification condition.
let limit = num rules + 1
let maxStratum = 0
# initialize stratumMap
foreach rule in ruleSet.rules:
stratumMap.set(rule, 0)
endfor
boolean changed = true
while changed:
changed = false
foreach edge E in DP:
# Edge from pRule to qRule with a label
let pRule = source of edge
let qRule = destination of the edge
let label = edge label
if label == "open":
if stratumMap.get(pRule) < stratumMap.get(qRule):
stratumMap.set(pRule, stratumMap.get(qRule))
changed = true
endif
endif
if label == "closed":
if stratumMap.get(pRule) <= stratumMap.get(qRule):
let xStratum = 1 + stratumMap.get(qRule)
if xStratum > limit:
# Stratification requirement violated
error "Stratification error"
endif
stratumMap.set(pRule, xStratum)
maxStratum = max(maxStratum, xStratum)
changed = true
endif
endif
endfor
endwhile
# Initialize the result map.
let stratumRules be a map from integer to rules.
foreach i = 0 to maxStratum
stratumRules.set(i, {})
endfor
# Gather rules in stratumMap with the same level number
foreach rule R in map stratumMap:
let stratumNum = stratumMap.get(R)
add R to stratumRules.get(stratumNum)
endfor
# Partition each level into once and general
let stratumLevels be a sequence of pairs of sets of rules.
for i = 0 to maxStratum:
let rules = stratumRules.get(i)
let once = { R in rules | R is a run-once rule }
let general = rules \ once
stratumLevels.set(i, pair(once, general))
endfor
the result is stratumLevels
enddefine
A step-by-step application of dependency analysis and
stratification to a complete rule set, followed through to
evaluation, is given in
6.6 Worked Example.
4.5 Processing Imports
Reading documents from the web has security implications.
Support for importing rule sets is optional for SPARQL-RL processors.
Further, implementations MAY provide partial support,
such as supporting imports of certain rule sets and not others,
and possibly from a verified copy.
The following conditions apply to imports processing:
Implementations that do not support importing rule sets MUST reject
a rule set that contains IMPORTS statements and signal an error.
An implementation that provides partial support
MUST signal an error if it encounters an import
that it does not support.
An implementation MUST signal an error if it cannot resolve the import document,
or if the document is not syntactically valid.
Processors MUST import a rule set only once to avoid infinite loops
when processing IMPORTS statements.
A resolved rule set is produced from another rule set by
recursively reading all rule sets mentioned
in the imports of that other rule set.
SRL and SPARQL have a close relationship. SRL is designed to be compatible
with SPARQL, and many of the constructs in SRL are taken from, or inspired by,
SPARQL pattern matching. However, there are some differences.
In SRL, RULE variables are always bound before use, whether used in an
expression of FILTER or SET, or used in triple templates of the
rule head. SPARQL CONSTRUCT queries and INSERT updates will
produce partial results if a variable occurs in the CONSTRUCT or
INSERT template but is not given a value in the WHERE clause.
The SRL SET form and SPARQL BIND form have different
error-handling behavior. An error encountered in SET causes the
current solution to be filtered out, whereas BIND does not
set the variable in the current solution but passes on the solution.
SET(?var := expr) would be the same as
SPARQL with
BIND(expr AS ?var) followed by
FILTER(BOUND(?var)).
The syntax of a rule body WHERE clause
does not include UNION or OPTIONAL syntax.
These SPARQL elements can lead to unbound variables.
The effect of UNION or OPTIONAL can be achieved using
well-formed rules.
Other differences include:
The syntax of NOT limits the inner body to triple
patterns and filters, and does not allow nested patterns.
NOT executes as a filter at the point in the rule body
where it is written, unlike SPARQL FILTER NOT EXISTS.
Property path syntax only covers paths with / and ^.
These can be expanded into triple patterns.
It does not allow the arbitrary length operators * and +.
Arbitrary length paths can be expressed in SPARQL-RL
with recursion as a more general approach.
Some functions are not included in the SRL syntax. There is no
COALESCE or BOUND. There are no hash functions. There
is no RAND, because it has different results each time it is
called.
Note
NOW() is permitted and is defined to return the same
point in time throughout a rule set evaluation.
Using BNODE produces different blank nodes on each call. The
result of rule set evaluation will produce inference graphs that are
graph isomorphic.
UUID and STRUUID can be used to generate unique identifiers.
Rules should not inspect these generated identifiers, only use them
to generate triples.
Specialized generators can be used for testing reproducibility,
similar to testing the outcome of NOW.
6. Rule Set Evaluation
This section defines the outcome of evaluating a rule set on given data.
Implementations are not required to use this algorithm.
An implementation can use any algorithm that generates the same outcome.
Inputs: graph G, called the base graph, and a rule set RS.
Output: an RDF graph GI of inferred triples
The inferred triples do not include triples present in
the base graph.
A solution mapping, μ, is a partial function
μ : V → T,
where V is the set of all variables
and T is the set of all RDF terms.
The domain of μ is denoted
by dom(μ), and it is the subset
of V for which μ is defined. The term
solution can be used when it is clear that a solution mapping is meant.
Write μ0 for the solution mapping, such that
dom(μ0) is the empty set.
The template instance function is a function
replaceBlankNodes(list of triple templates) that
returns a list of triple templates where each blank node
in the argument is replaced by a fresh blank node.
Multiple occurrences of the same blank node
are replaced by the same fresh blank node.
A graph match finds the ways to
map a triple pattern onto triples in an RDF graph.
Let G be an RDF graph and TP be a triple pattern.
The function graphMatch(G, TP) returns a set of all possible
solutions that,
when applied to the triple pattern, produce a triple that is in
graph G.
Let G be an RDF graph, TP be a triple pattern,
and V be the set of variables occurring in TP.
graphMatch(G, TP) = { μ | dom(μ) = V and subst(μ, TP) is a triple in G }
Solution compatible
Two solutions S1 and S2 are compatible if they agree on the variables in common.
Let S1 and S2 be solutions.
compatible(μ1, μ2) = true
if forall v in dom(μ1) intersection dom(μ2)
μ1(v) = μ2(v)
compatible(μ1, μ2) = false otherwise
Solution sequence
A solution sequence is a multi-set of solutions.
There is no defined order to the sequence.
It is equivalent to an unordered list and it can contain duplicates.
Solution merge
If two solutions are compatible, the merge of two solutions is the solution
that maps variables of each solution to the RDF term
from one or other of the solutions.
Let μ1, μ2
be solution mappings, and S1 and S2 be solution sequences.
merge(μ1, μ2) = μ such that
μ(v) = μ1(v) if v in dom(μ1)
μ(v) = μ2(v) otherwise
merge(S1, S2) = { μ |
μ1 in S1, μ2 in S2
and compatible(μ1, μ2)
μ = merge(μ1, μ2) }
Note
The domain of merge(μ1, μ2)
is domain(μ1) ∪ domain(μ2).
If the two solutions have no variables in common, then they are compatible,
and the merge of the two solutions is the union of
μ1 and μ2.
An expression, whether used in a filter element or
an assignment element, is evaluated with
respect to a solution mapping. The solution mapping provides the
RDF term values for each variable in the expression.
The well-formedness requirements of 4.2 Well-formedness Conditions
ensure that all variables in the expression
appear in the solution mapping.
define evalFunction(F, μ):
# F is an expression: an RDF term, a variable, or op(expr1, ..., exprN)
# where op is a function or a functional form.
# μ is a solution mapping
# Any error during evaluation causes evalFunction to return an error.
if F is an error:
return error
if F is an RDF term:
return F
if F is a variable:
# By well-formedness, F ∈ dom(μ).
return μ(F)
# F is of the form F = op(expr1, ..., exprN)
if op is a functional form (e.g., IF, logical-or):
# Evaluated specifically for op; op may evaluate only some arguments.
# For example, IF(c, t, f) evaluates c, then exactly
# one of t or f is evaluated.
return the value defined for op over expr1, ..., exprN under μ
# op is an ordinary function: evaluate all arguments first.
return op(evalFunction(expr1, μ), ..., evalFunction(exprN, μ))
enddefine
Blank nodes are treated as variables within triple patterns of a
rule body by replacing each blank node by a variable which is
not used in the rule.
This includes replacing blank nodes inside triple terms.
The same variable is used for each occurrence of
the same blank node, and a different variable is used for each
different blank node.
# Evaluate rule body
# This function returns a sequence of solutions
define evalRuleElements(B, SEQ, G, GD):
where
B is a sequence of rule elements
SEQ is a solution sequence
G and GD are RDF graphs
foreach rule element rElt in B:
if rElt is a triple pattern element TP:
X = graphMatch(G, TP)
SEQ1 = {}
foreach μ1 in X:
foreach μ2 in SEQ:
if compatible(μ1, μ2):
μ3 = merge(μ1, μ2)
add μ3 to SEQ1
endif
endfor
endfor
endif
if rElt is a filter element F:
SEQ1 = {}
foreach solution μ in SEQ:
let x = evalFunction(F.expr, μ)
if x is not an error and EBV(x) is true:
add μ to SEQ1
endif
endfor
endif
if rElt is a negation element N:
SEQ1 = {}
foreach solution μ in SEQ:
S = sequence{ μ }
if N.evaldata:
NEG = evalRuleElements(N.inner, S, G, GD)
else:
NEG = evalRuleElements(N.inner, S, GD, GD)
endif
if NEG is empty:
add μ to SEQ1
endif
endfor
endif
if rElt is an assignment A:
SEQ1 = {}
foreach solution μ in SEQ:
let x = evalFunction(A.expr, μ)
if x is not an error:
# Add mapping A.var -> x to solution μ
let μ2 be a solution mapping μ ∪ { (A.var, x) }
add μ2 to SEQ1
else:
# Error: drop solution μ
endif
endfor
endif
SEQ = SEQ1
endfor
return SEQ
enddefine
define evalRule(R, G, GD):
where
R is a well-formed rule
G and GD are RDF graphs
let B be R.body
treating blank nodes as variables.
# Solution sequence of one solution that does not map any variables.
let SEQ0: Solution sequence = { μ0 }
if R.evaldata:
let SEQ = evalRuleElements(B, SEQ0, G, GD)
else:
let SEQ = evalRuleElements(B, SEQ0, GD, GD)
endif
# Evaluate rule head
let OUT = empty set
foreach μ in SEQ:
let S = {}
# Rule head with each blank node replaced by a fresh blank node
let HT = replaceBlankNodes(R.head)
foreach triple template TT in HT
let triple = subst(μ, TT)
Add triple to S
endfor
OUT = OUT ∪ S
endfor
return OUT
enddefine
Note
OUT may contain triples that are also in the base graph.
6.5 Evaluation of a Rule Set
Evaluation of a rule set is defined as the execution of each stratum of a
stratification of the rule set, where each stratum is executed completely
and in order before moving on to the next stratum.
A stratum is evaluated by first evaluating
each of the run-once rules of that stratum, and then evaluating
general rules of the stratum repeatedly until no new triples are produced.
let G0 be the input base graph
let RS be the rule set
let D be the graph of all DATA triples in RS
Apply stratification to RS
let LS be the sequence of layers after stratification
# Inference graph
let GI = { t ∈ D | t ∉ G0 }
# Evaluation graph and data blocks
let GE = G0 ∪ D
foreach stratum ST in LS:
foreach rule R in ST.once:
let X = evalRule(R, GE, G0)
let Y = { t ∈ X | t ∉ GE }
GI = GI ∪ Y
GE = GE ∪ Y
endfor
let finished = false
while ! finished:
finished = true
foreach rule R in ST.general:
let X = evalRule(R, GE, G0)
let Y = { t ∈ X | t ∉ GE }
if Y is not empty:
finished = false
GI = GI ∪ Y
GE = GE ∪ Y
endif
endfor
endwhile
endfor
the result is GI
The example describes software components and their dependencies:
a frontend depends on an application server, which depends on a
database and on a logging library. The database has a known
vulnerability. The rules propagate exposure to vulnerabilities
along the dependency chain, give components exposed to a severe
vulnerability the status :criticallyExposed, give components that are
not critical the status :safeToDeploy, and create a
notification for each critically exposed component.
(In practice, whether a vulnerability affects a component
depends on the deployed version; the example elides versions and
states the vulnerability directly.)
For brevity, the base graph states :dependsOn triples directly,
rather than deriving them from more specific relations as in
3.1 Triple Patterns.
The rules are labeled R1 to R5 in comments and are referred
to by these labels in the rest of this section.
They are the rules introduced in
3.2 Recursion through
3.5 Assignment and Creating RDF Terms.
The rule set has no IMPORTS, so import processing
leaves it unchanged, and no DATA blocks, so evaluation starts
from the base graph alone.
6.6.1 Determining the Dependencies
Each triple pattern in each rule body is compared with the
triple templates in every rule head, to determine which rules
depend on which
(4.3 Rule Dependency).
The body of R1 is the single triple pattern
?x :hasVulnerability ?v. No rule head has a triple template
that can generate a triple with predicate :hasVulnerability,
so this pattern can only match the data.
R1 has no dependencies.
The body of R2 has two triple patterns.
?x :dependsOn ?y cannot match any rule head, so it matches
only the data. ?y :exposedTo ?v matches the head template
?x :exposedTo ?v of R1, and also matches the head of R2
itself. Both occurrences are triple pattern elements
(they do not occur inside a negation element, and R2 is
not a run-once rule), so
R2 has an open dependency on R1 and an
open dependency on itself.
The dependency of R2 on itself makes R2 a recursive rule.
In the body of R3, the pattern ?x :exposedTo ?v matches
the heads of R1 and R2, giving R3 an open
dependency on each. The pattern ?v :severity ?s matches no
rule head.
In the body of R4, the pattern ?x rdf:type :Component
matches no rule head: the only head template with predicate
rdf:type is in R5, and its object :Notification is
a different RDF term from :Component, so no generated
triple can match.
The pattern ?x :status :criticallyExposed occurs inside the
negation elementNOT { ?x :status :criticallyExposed } and
matches the head template of R3. Because the pattern
occurs in a negation element, R4 has a closed
dependency on R3.
In the body of R5, the pattern ?x :status :criticallyExposed
matches the head of R3. The head of R5 contains a
blank node, so its dependency on R3 is a closed
dependency, even though the pattern is an ordinary
triple pattern element.
No pattern in any rule body matches the head templates of
R5, so no rule depends on R5.
Although R4 and R5 have no direct dependency on R1 or
R2, each has a transitive dependency on both, through
R3.
Figure 1
The dependency graph of the worked example rule set.
Open dependencies are drawn as dashed arrows and closed
dependencies as solid arrows. Each edge points from the
rule whose body contains the matching triple pattern to the
rule whose head could generate the matching triples.
The only cycle in the graph is the self-edge R2 → R2,
which is an open dependency. No cycle involves a closed
dependency, so the stratification condition is satisfied
and the rule set has a well-defined outcome.
6.6.2 Calculating the Stratification
Following the
stratification algorithm,
every rule starts in stratum 0. The edges are then inspected
repeatedly until nothing changes:
An open edge requires the source rule to be in the
same stratum as its target or higher. All four open edges
already satisfy this with every rule at stratum 0, so they
cause no changes.
A closed edge requires the source rule to be in a
strictly higher stratum than its target, because the target
must run to completion first. The edge R4 → R3
(closed) finds R4 and R3 both at stratum 0, so R4 is
moved to stratum 1. Likewise the edge R5 → R3
(closed) moves R5 to stratum 1.
A further pass over the edges makes no changes, so the strata
are final. Each stratum is then partitioned into
run-once rules and general rules. R5 has a blank
node in its head, so it is a run-once rule; no other rule
of the rule set is a run-once rule.
The stratification is:
Stratum 0: general R1, R2, R3; no run-once rules
Stratum 1: run-once R5; general R4
This ordering captures the intent of the rules in the higher
stratum. Whether a component is safe to deploy, and which
components need a notification, can only be decided after
all:status :criticallyExposed triples have been derived
— and the rule that derives them, R3, completes in the
stratum below, together with the rules R1 and R2 that
feed it.
6.6.3 Evaluating the Strata
Evaluation follows the algorithm of
6.5 Evaluation of a Rule Set.
The evaluation graph GE starts as the base graph and the
inference graph GI starts empty. Each stratum is evaluated to
completion in order: the rules of the stratum are evaluated in
passes, and passes repeat until a pass produces no new triples.
The algorithm does not fix the order in which the rules of a
stratum are evaluated within a pass; this trace uses the order
R1, R2, R3. A different order can spread the same
inferences across a different number of passes but, because
stratum 0 runs to completion, it produces the same final graph.
Because this rule set has no DATA blocks, GE is G0 plus
GI at every point in the evaluation. The trace therefore
tracks only GI, showing its state as evaluation proceeds and
marking each new triple with the rule that produced it.
Stratum 0, first pass.
R1: the body matches
:db :hasVulnerability :vuln1, binding
?x = :db and ?v = :vuln1.
The head produces :db :exposedTo :vuln1.
The triple is not in GE, so it is added to GE and GI.
R2: the body joins ?x :dependsOn ?y with
?y :exposedTo ?v. GE now contains
:db :exposedTo :vuln1, so the join yields one solution:
?x = :app, ?y = :db, and ?v = :vuln1
(from :app :dependsOn :db).
The head produces :app :exposedTo :vuln1, which is new and
is added. There is no solution for :frontend yet, because
:app :exposedTo :vuln1 was not in GE when this
evaluation of R2 started.
R3: ?x :exposedTo ?v now matches for :db and :app;
joining with :vuln1 :severity 9.1 and applying
FILTER(?s >= 9.0) keeps both solutions.
The head produces :db :status :criticallyExposed and
:app :status :criticallyExposed, both new.
# GI after stratum 0, first pass
:db :exposedTo :vuln1 . # new (R1)
:app :exposedTo :vuln1 . # new (R2)
:db :status :criticallyExposed . # new (R3)
:app :status :criticallyExposed . # new (R3)
New triples were produced, so evaluation of stratum 0
continues with another pass.
Stratum 0, second pass.
R1: matches as before; :db :exposedTo :vuln1 is already
in GE, so nothing new is produced.
R2: the join now also yields
?x = :frontend, ?y = :app, and ?v = :vuln1, producing
the new triple :frontend :exposedTo :vuln1.
The exposure has taken two passes to travel two steps along
the dependency chain.
R3: produces the new triple
:frontend :status :criticallyExposed.
# GI after stratum 0, second pass
:db :exposedTo :vuln1 .
:app :exposedTo :vuln1 .
:frontend :exposedTo :vuln1 . # new (R2)
:db :status :criticallyExposed .
:app :status :criticallyExposed .
:frontend :status :criticallyExposed . # new (R3)
Stratum 0, third pass.
Every solution of every rule now produces only triples already
in GE. GI is unchanged.
No new triples means stratum 0 is complete: every
:exposedTo triple and every :status :criticallyExposed triple that
can ever be derived has been derived.
Stratum 1, run-once rules.
The run-once rules of the stratum are evaluated first,
each exactly once.
R5: the body matches the three :status :criticallyExposed
triples, giving the solutions ?x = :db, ?x = :app, and
?x = :frontend. For each solution, instantiating the head
creates a fresh blank node, producing two triples
per solution which are notifications for each critical
component. R5 is not evaluated again, even though the
general rules of the stratum will now be evaluated
repeatedly.
Stratum 1, first pass of the general rules.
R4: the pattern ?x rdf:type :Component matches
:frontend, :app, :db, and :logger.
(It does not match the rdf:type :Notification triples
just created by R5.)
The negation element NOT { ?x :status :criticallyExposed } rejects
the solutions for :frontend, :app, and :db, because
GE contains a :status :criticallyExposed triple for each of them.
Only the solution ?x = :logger survives, producing the new
triple :logger :status :safeToDeploy.
# GI after stratum 1
:db :exposedTo :vuln1 .
:app :exposedTo :vuln1 .
:frontend :exposedTo :vuln1 .
:db :status :criticallyExposed .
:app :status :criticallyExposed .
:frontend :status :criticallyExposed .
_:n1 rdf:type :Notification . # new (R5)
_:n1 :concerns :db . # new (R5)
_:n2 rdf:type :Notification . # new (R5)
_:n2 :concerns :app . # new (R5)
_:n3 rdf:type :Notification . # new (R5)
_:n3 :concerns :frontend . # new (R5)
:logger :status :safeToDeploy . # new (R4)
Stratum 1, second pass of the general rules.
No new triples. Evaluation is complete, and GI as shown
above is the resulting inference graph.
The stratification is what makes this outcome reliable.
Evaluated during the first pass of stratum 0, before
:frontend :status :criticallyExposed was derived, R4 would have
incorrectly concluded :frontend :status :safeToDeploy, and
R5 would have created notifications for :db and :app
but none for :frontend.
Deferring both to stratum 1 means they see the complete set of
:status :criticallyExposed triples, so the order in which
rules are evaluated within each stratum does not affect the
final outcome.
7. SPARQL-RL Grammar
A SPARQL-RL document
is an RDF string encoded in UTF-8 [RFC3629] and starting with the
RuleSet
production and conforming to the additional constraints defined in
7.6 Grammar.
Only Unicode scalar values,
in the ranges U+0000 to U+D7FF
and U+E000 to U+10FFFF,
are allowed. This excludes
surrogate code points,
range U+D800 to U+DFFF.
7.1 Version Announcement
A version label is a string that identifies the syntax and semantics
conformance for SPARQL-RL.
Version Labels
Version Label
"1.2"
The version announcement SHOULD be made early in the document.
Multiple VERSION directives
may appear in a SPARQL-RL document.
Each directive applies to the part of the document following the directive,
until another directive is encountered or the end of the document is reached.
Version labels can also be given by the version parameter of the
Media Type. In the absence of a current
VERSION directive, the
version specified as part of the Media Type is considered.
7.2 White Space
White space
(production WS) is used
to separate two terminals that would otherwise be incorrectly
recognized as one terminal.
Rule names in capitals below indicate where white space is
significant; these form a possible choice of terminals for constructing a
SPARQL-RL parser.
White space is significant in the production
String.
A Unicode code point
in the ranges U+0000 to U+D7FF
and U+E000 to U+FFFF,
corresponding to the value encoded by the four hexadecimal digits interpreted
from most significant to least significant digit.
A Unicode code point
in the ranges U+0000 to
U+D7FF
and U+E000 to U+10FFFF,
corresponding to the value encoded by the eight hexadecimal digits
interpreted from most significant to least significant digit.
A string escape sequence represents a character traditionally escaped in string literals:
Escape sequence
Unicode code point
\t
U+0009
\b
U+0008
\n
U+000A
\r
U+000D
\f
U+000C
\"
U+0022
\'
U+0027
\\
U+005C
A reserved character escape sequence consists of a
\ followed by
one of these characters ~.-!$&'()*+,;=/?#@%_, and
represents the character to the right of
the \.
Context where each kind of escape sequence can be used
%-encoded sequences are in the
character range for IRIs
and are explicitly allowed in local names.
These appear as a %
followed by two hex characters and represent that
same sequence of three characters. These sequences are not
decoded during processing.
A term written as <http://a.example/%66oo-bar>
designates the IRI http://a.example/%66oo-bar
and not IRI http://a.example/foo-bar.
A term written as ex:%66oo-bar with a prefix
PREFIX ex: <http://a.example/>
also designates the IRI http://a.example/%66oo-bar.
7.6 Grammar
The EBNF used here is defined in XML 1.0
[EBNF-NOTATION].
This document uses some terminal literal strings
[EBNF-NOTATION]. To clarify the Unicode code points used for these
terminal literal strings, the following table describes the specific
characters used.
Code
Glyph
Description
U+000A
LF
Line feed
U+000D
CR
Carriage return
U+0023
#
Number sign
U+0025
%
Percent sign
U+005C
\
Backslash
A. Translation of SPARQL-RL to SPARQL
Issue 1303: SRL: Provide an algorithm to show a translation of SRL to SPARQL Query SPARQL-RL
Provide an algorithm to show a translation of SPARQL-RL to SPARQL Query.
B. Example Imports Algorithm
This section is non-normative.
The following algorithm shows one way to resolve IMPORTS statements by
visiting all the referenced documents recursively.
The rule set merge of two rule sets, RS1 and RS2,
produces a rule set, MR, defined as follows:
let RS be a rule set
let V = {}
if RS has a location:
V = { location of RS }
endif
define ruleSetMerge(rule set RS1, rule set RS2):
let MR be a rule set
MR.rules = RS1.rules ∪ RS2.rules
MR.data = rdf_merge(RS1.data, RS2.data)
MR.imports = {}
the result is MR
enddefine
define imports(rule set RS):
let RS2 be a rule set formed from RS.rules and RS.data
foreach URL x in RS.imports:
if x ∉ V:
V = V ∪ { x }
read rule set RS3 from URL x
RS2 = ruleSetMerge(RS2, imports(RS3))
endif
endfor
the result is RS2
enddefine
result is imports(RS)
The Internet Media Type (formerly known as MIME Type) for
SPARQL-RL is "application/sparql-rl".
The information that follows has been submitted to the Internet Engineering
Steering Group (IESG) for review, approval, and registration with IANA.
Type name:
application
Subtype name:
sparql-rl
Required parameters:
None
Optional parameters:
version
This parameter is optional.
If present, acceptable values of version are defined in
Version Labels.
profile
This parameter is optional and is used to include additional information.
It does not change the semantics of the resource representation when
processed without knowledge of the profile. The value of a
profile parameter is a non-empty list of space-separated URIs.
For more information and background, please refer to [RFC6906].
Encoding considerations:
The syntax of SPARQL-RL is expressed over code points in Unicode
[UNICODE]. The encoding is always UTF-8 [RFC3629].
Unicode code points may also be expressed using an \uXXXX (U+0 to
U+FFFF) or \UXXXXXXXX syntax (for U+10000 onward)
where X is a hexadecimal digit [0-9A-Fa-f],
excluding U+D800 to U+DFFF,
the surrogate code points.
A SPARQL-RL file may have the string 'PREFIX'
(case independent) near the beginning
of the document.
File extension(s):
".srl"
Base URI:
The SPARQL-RL 'BASE <IRIref>' term can change the
current base URI for resolving IRIrefs in the language.
Email address to contact for further information:
Data Shapes Working Group <public-shacl@w3.org>
Intended usage:
COMMON
Restrictions on usage:
None
Author/Change controller:
The SPARQL-RL specification is a work product of the
World Wide Web Consortium's Data Shapes Working Group.
The W3C has change control over this specification.
D. Security Considerations
This section is non-normative.
SPARQL-RL documents may contain IMPORTS statements that reference other
SPARQL-RL documents and import their contents into the current document.
If an imported document itself contains its own IMPORTS statements,
those documents are also imported.
While useful to modularizing rule sets, the use of IMPORTS statements can
introduce security risks.
Risks include, but are not limited to, rule sets
causing excessive computation, whether maliciously or accidentally, while being evaluated;
and HTTP requests being intercepted and a different document being returned,
including out-of-date copies.
Applying a SPARQL-RL rule set to an RDF graph can result in
significant computation and memory usage, which may be exploited
to cause denial of service.
Applications should take care to limit the amount of computation and
memory usage that can be caused by applying a SPARQL-RL rule set.
The SPARQL-RL syntax is encoded in UTF-8 [RFC3629] and allows
the use of unescaped control characters in string data.
Although this specification does not directly expose this content to an end user,
it might be presented through a user agent, which may cause the presented text to
be misleading due to such characters.
SPARQL-RL can be used to process and create arbitrary application data;
security considerations will vary by domain of use.
Security tools and protocols applicable to text
(for example, PGP encryption, checksum validation, password-protected compression)
may also be used on SPARQL-RL documents.
Security/privacy protocols must be imposed to reflect the sensitivity of the
information in the outcome of SPARQL-RL rule set evaluation.
The security considerations of SPARQL-RL include those of
RDF data and formats such as
RDF Turtle.
E. Privacy Considerations
This section is non-normative.
A SPARQL-RL document can contain additional application data
which may include the expression of personally identifiable information (PII)
or other information which could be considered sensitive.
Authors publishing rule sets with such information are advised to carefully
consider the needs and use of publishing such information,
as well as the applicable regulations for the regions where the data is
expected to be consumed and potentially revealed (e.g.,
GDPR,
CCPA,
others),
particularly whether authorization measures are needed for access to the data.
F. Acknowledgments
This section is non-normative.
The following people contributed to the development of SPARQL-RL in the
rules task force of the Data Shapes Working Group:
Robert David, David Habgood, Livio Robaldo, Ognjen Savkovic,
Simon Steyskal, Ted Thibodeau Jr, and Andy Seaborne.
Members of the Data Shapes Working Group included @@.