SHACL 1.2 Rules

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

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.

TODO

: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.

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

# 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)
}

IMPORTS

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 element

A condition element is an expression that evaluates to true or false. Condition elements 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 elements.

Assignment element

An assignment element is a pair consisting of a variable, called the assignment variable, and an expression, called the assignment expression. Assignment elements 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 element, a negation element, or an assignment element.

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 produced by evaluating a rule set. It contains all triples not present in the base graph that are inferred from applying the rule set to the base graph.

Infer

Infer is the operation that applies the rules to a given base graph and produces an inference graph containing inferred triples. triples derived from rule execution.

Query

Query is the operation that determines whether a given goal pattern can be derived from a base graph using the rules.

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 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 element 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 element 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 element 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 element 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".

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.

  Editor's note

  Revise

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

Examples:

@@ Examples of triple patttern dependencies.

@@ Examples of rule dependencies.

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".

## output -- Map: Integer -> Set of rules.

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.
    ## Check unbounded work due to a violation of the stratification condition.
    let limit = num rules  + 1
    let maxStratum = 0

    ## initialize stratumMap
    foreach rule in ruleSet:
        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 == "positive" :
                if stratumMap.get(pRule) < stratumMap.get(qRule) :
                    stratumMap.set(pRule, stratumMap.get(qRule))
                    changed = true;
                    endif
                endif
            if label == "negative" :
                if stratumMap.get(pRule) <= stratumMap.get(qRule) :
                    let xStratum = 1 + stratumMap.get(qRule)
                    if ( xStratum > limit )
                        ## Stratification requirement violated
                        error "Stratification error"
                        endif
                    stratumMap.put(pRule, xStratum)
                    maxStratum = max(maxStratum, xStratum)
                    changed = true;
                    endif
                endif
            endfor
        endwhile

    ## Initialize the result map.
    let stratumLevels be a map from integer to a set of rules
    for i = 0 to maxStratum
        stratumLevels.set(i, {})
        endfor

    ## Gather rules in stratumMap with the same level number
    for rule R in map stratumMap:
        let stratumNum = stratumMap.get(R)
        let S = {R} ∪︀ stratumLevel.get(stratumNum)
        stratumLevel.set(stratumNum, S)
        endfor

    the result is stratumLevels
    endfunction

The grammar is given below.

Vocabulary: shacl-rules.ttl.

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)

Editor's note

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

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

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 pattern elements,
                condition elements, negation elements,
                and assignment elements 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
                    endif
                endfor
             endfor

        if rElt is a condition element 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
        endfor
    H = H union S
    endfor

result eval(R, G) is H

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