Terminology

Connect to definitions in RDF 1.2 Concepts.

The following definitions from other specifications are used in this document: @@

TODO

RFC 2119 language should be automatically inserted here.

Basic Usage

   :A :fatherOf :X .
   :B :motherOf :X .
   :C :motherOf :A .

RULE { ?x :childOf ?y } WHERE { ?y :fatherOf ?x }
RULE { ?x :childOf ?y } WHERE { ?y :motherOf ?x }

RULE { ?x :descendedFrom ?y } WHERE { ?x :childOf ?y }
RULE { ?x :descendedFrom ?y } WHERE { ?x :childOf ?z . ?z :childOf ?y }

The above rules, applied to the data, will conclude that: `:X` is the `:childOf` `:A` and `:B`, and that `:X` is `:descendedFrom` `:C`.

Recursion

RULE { ?x :ancestorOf ?y } WHERE { ?y :descendedFrom ?x }
RULE { ?a :ancestorOf ?b } WHERE { ?a :ancestorOf ?c . ?c :ancestorOf ?b }

Negation

# Default value - calculate a name
RULE { ?x :name ?FN } WHERE { 
    ?x rdf:type :Person 
    NOT { ?x :name ?someName }
    ?x :givenName ?name1 ;
       :familyName ?name2 .
    BIND(concat(?name1, " ", ?name2) AS ?FN)
}

Importing rules

`IMPORTS`

Assignment and Creating RDF Terms

Rule Tuples

Attaching Rules To Shapes

[] rdf:type sh:NodeShape ;
    sh:rule                   ## Different property?
      [ a srl:SHACLRule ;
        srl:ruleSet "...";    ## SRL syntax
        sh:prefixes ... ;
      ];
[] rdf:type sh:NodeShape ;
    sh:rule
      [ a srl:SHACLRule ;
        srl:ruleSet [ ... RDF syntax ... ] ;
      ];

Relationship between `RULE` and SPARQL `CONSTRUCT`

Elements of the Abstract Syntax

Variable

A [=variable=] represents a possible [=RDF term=] in a triple pattern. Variables are also used in expressions.

Expression

An [=expression=] is a function, or functional form. It's arguments are [=RDF terms=]. An expression is evaluated with respect to a [=solution mapping=] to give an [=RDF term=] as the result. Expressions are compatible with SHACL list parameter functions and with SPARQL expressions.

Data block

A [=data block=] is a set of triples. These form extra facts that are included in the inference process.

Triple template

A [=triple template=] is 3-tuple where each element is either a [=variable=] or an [=RDF term=] (which might be a [=triple term=]). The second element of the tuple must be an [=IRI=] or a [=variable=]. [=Triple templates=] appear in the [=head=] of a [=rule=].

Triple pattern

A [=triple pattern=] is 3-tuple where each element is either a [=variable=] or an [=RDF term=] (which might be a triple term). The second element of the tuple must be an [=IRI=] or a [=variable=]. [=Triple patterns=] can appear as [=triple pattern elements=] as well as inside [=negation elements=].

Condition expression

A [=condition expression=] is a function, or functional form, that evaluates to true or false. [=Condition expressions=] appear in the [=body=] of a [=rule=].

Triple pattern element

A [=triple pattern element=] is a [=triple pattern=] used as a [=rule body element=].

Negation element

A [=negation element=] is a [=rule body element=]. It takes a sequence of [=triple patterns=] and [=condition expressions=].

Assignment

An [=assignment=] is a pair of a variable, called the assignment variable, and an expression, called the assignment expression. [=Assignments=] appear in the [=body=] of a [=rule=].

Rule body element

A [=rule body element=] (often just "rule element") is any element that can appear in a [=rule body=], a [=triple pattern=], a [=condition expression=], a [=negation element=], or an [=assignment=].

Rule head

A [=rule head=] is a sequence of [=triple templates=].

Rule body

A [=rule body=] is a sequence of [=rule body elements=].

Rule

A [=rule=] is a pair of a [=rule head=] (often just "head") and a [=rule body=] (often just "body").

Rule set

A [=rule set=] is a collection of zero or more [=rules=] and a collection of zero or more [=data blocks=].

Base graph

The [=base graph=] is the [=RDF Graph=] given as input to the evaluation process.

Inference graph

The [=inference graph=] is an [=RDF Graph=] that is the outcome of rule set evaluation. It contains all triples not found in the [=base graph=] that are inferred from evaluation of the [=rule set=] on the [=base graph=].

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.

Well-formedness Conditions

Well-formedness is a set of conditions on the abstract syntax of SHACL rules. 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 an [=condition expression=] or [=assignment expression=] has a value at the point of evaluation; and that each assignment in a rule introduces a new variable, one that has not been used earlier in the rule body.

A [=rule=] is a well-formed rule if all of the following conditions are met:

• For every [=variable=] appearing in a [=triple template=] of the [=head=] of the [=rule=], there is one or more occurrences of a [=variable=] of the same name in the [=triple patterns=] in the [=body=], in an [=assignment=] in the body, or both.
• For every [=variable=] in an [=expression=] at position i of the [=body=], there is a corresponding [=variable=] of the same name occurring in a [=triple pattern=] at a position j, or occurring as an [=assignment variable=] at a position j, where i > j.
• Each [=assignment variable=] is used in only one [=assignment=] in the [=body=] of the [=rule=].
• An [=assignment variable=] at position i of a [=rule body=] does not occur in any [=triple pattern=] at position j where i > j.
• For every [=variable=] in an [=assignment expression=] at position i, there is a corresponding variable in a [=triple pattern=] at position j where i > j, or there is an [=assignment variable=] in an [=assignment=] at position j where i > j.

A [=rule set=] is "well-formed" if and only if all of the [=rules=] of the rule set are "well-formed".

Rule Dependency

Triple pattern dependency

A [=triple pattern=] in the rule body of rule `R1` depends on a rule `R2` if the head of `R2` can possibly generate triples that match the [=triple pattern=] in `R1`. The dependency is positive if the [=triple pattern=] is a [=rule body element=] and the dependency is negative if the [=triple pattern=] appears in a [=negation element=].

Rule dependency

A rule `R1` depends on rule `R2` if any rule element of `R1` depends on `R2`. The dependency is negative if any of the rule elements have a negative dependency on `R2`; otherwise the dependency is positive.

Dependency graph

A [=dependency graph=] of a [=rule set=] is a graph where the vertices are rules and an edge exists where one rule R1 depends on rule R2. An edge is labeled either positive or negative according to the [=rule dependency=].

Transitive rule dependency

A rule `R1` has a [=transitive dependency=] on rule `R2` if there is a path in the [=dependency graph=] from `R1` to `R2`.

Recursive rule dependency

A rule `R` has a [=recursive dependency=] if there is a cyclic path in the [=dependency graph=] involving `R`.

Notes:

• A [=triple template=] with components `ts`, `tp`, `to` can possibly generate a triple with component RDF terms `s`, `p`, `o` if `ts` is a variable or `ts` is the same RDF term as `s`, `tp` is a variable or `tp` is the same RDF term as `p`, and `to` is a variable or `to` is the same RDF term as `o`.

  In addition, if any pair of `ts`, `tp`, and `to` are the same variable, then the corresponding pair of `s`, `p`, and `o` must be the same.

  Revise

• The dependency graph is not affected by the data graph.

Examples:

            @@ Examples of triple patttern dependencies.
          

            @@ Examples of rule dependencies.
          

Stratification

[=Stratification=] is the process of partitioning a [=rule set=] into an ordered sequence of [=stratification layers=] (also known as "strata", singular "stratum="), forming a [=stratification=]. Rules in lower [=strata=] are evaluated before rules in higher [=strata=].

[=Stratification=] imposes constraints on dependencies between [=rules=] to ensure that [=negation elements=] depend only on results computed in earlier [=strata=], guaranteeing a single, well-defined outcome from the evaluation of a [=rule set=] over a given [=base graph=].

Stratification

A [=stratification=] of a [=rule set=] is a sequence of sets of rules. Each rule in a [=rule set=] appears in exactly one [=stratification layer=].

Stratification layer

Each set of rules in a [=stratification=] is called a [=stratification layer=], also called a "stratum".

              @@ one possible stratification algorithm
            

Shape Rules Language syntax

The grammar is given below.

Mapping the AST to the abstract syntax.

RDF Rules Syntax

Vocabulary: shacl-rules.ttl.

Evaluation Definitions

solution mapping

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. We use the term [=solution=] where it is clear that a [=solution mapping=] is meant. Write μ₀ for the solution mapping such that dom(μ0) is the empty set.

substitution function

A substitution function, or just substitution, is a function subst(μ, [=triple pattern=]) that returns a [=triple pattern=] where each occurrence in the [=triple pattern=] of a variable that is in the dom(μ) is replaced by the [=RDF term=] given by the [=solution mapping=] for var. If the triple pattern result has no variables, then it is an [=RDF Triple=].

evaluation graph

A [=evaluation graph=] is an [=RDF Graph=] that combines the [=base graph=] and all triples produced during the evaluation of a rule set.

graph match

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 the [=evaluation graph=]

Let G be an [=RDF graph=] and TP be a triple pattern.

graphMatch(G, TP) = { μ | 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 μ₁, μ₂ be solution mappings, and S1 and S2 be solution sequences.

merge(μ1, μ2) = { μ |
                    μ(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)
                    μ(v) = merge(μ1, μ2)

Say the domain is `dom(S1) ∪︀ dom(S2)`.

Say that two solutions that have no variables in common are compatible.

Evaluation of an Expression

Sketch

@@ Reference SPARQL expression evaluation Expression Evaluation
@@ Reference SPARQL EBV Effective Boolean Value (EBV)

define evalFunction(F, μ):
    Let [x/μ] be
        if x is an RDF term, then [x/row] is x
        if x is a variable, then [x/row] is μ(x)
        ## By well-formedness, it is an error if x is not in the row.
    eval(F(expr1, expr2 ...), row) = F(eval(expr1, row), eval(expr2, row), ...)
    eval(FF(expr1, expr2) , row) = ... things that are not functions like `IF`

Evaluation of a Rule

let R be a well-formed rule.

let rule R = (H, B) where
             H is the sequence of triple templates in the head
             B is the sequence of triple patterns,
                condition expressions, negation elements,
                and assignments in the body

# Solution sequence of one solution that does not map any variables.
let SEQ0: Solution sequence = { μ0 }

let G = evaluation graph

# Evaluate rule body
# This function returns a sequence of solutions
define evalRuleElements(B, SEQ, G):

    for each rule element rElt in B:

        if rElt is a triple pattern TP:
            X = graphMatch(G, TP)
            SEQ1 = {}
            for each μ1 in X:
                for each μ2 in SEQ:
                  if compatible(μ1, μ2)
                    μ3 = merge(μ1, μ2)
                    add μ3 to SEQ1
                endfor
            endif

        if rElt is a condition expression with expression F:
            SEQ1 = {}
            for each solution μ in SEQ:
                if evalFunction(F, μ) is true:
                    add μ to SEQ1
                    endif
                endfor
            endif

        if rElt is a negation expression with body elements N:
            SEQ1 = {}
            for each solution μ in SEQ:
                S = sequence{ μ }
                NEG = evalRuleElements(N, S, G)
                if NEG is empty
                    add μ to SEQ1
                    endif
                endfor
            endif

        if rElt is an assignment with variable V and expression expr
            SEQ1 = {}
            for each solution S in SEQ:
                let x = eval(expr, S)
                add(V, x) to S
                add S to SEQ1
                endfor
            endif

        if SEQ1 is empty
            SEQ = {}
            return SEQ
            endif

        SEQ = SEQ1
        endfor

     return SEQ
     enddefine

let SEQ = evalRuleElements(B, SEQ0, G)

# Evaluate rule head
let H = empty set
for each μ in SEQ:
    let S = {}
    for each triple template TT in head
        let triple = subst(μ, TT)
        Add triple to S
    H = H union S
    endfor

result eval(R, G) is H

Note that `H` may contain triples that are also in the data graph.

Evaluation of a Rule Set

Sketch

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 L be the sequence of layers after stratification

# Inference graph
let GI = { t ∈D  | t ∉ in G0 }

# Evaluation graph.
let GE = G0 ∪︀ D

for each layer in L:
    let finished = false
    while !finished:
        finished = true
        for each rule in layer:
            let X = eval(rule, GE)
            let Y = { t ∈ X | t ∉ in GE }
            if Y is not empty:
                finished = false
                GI = Y ∪︀ GI
                GE = Y ∪︀ GE
                endif
            endfor
        endwhile
    endfor
the result is GI