From Semantic Web Standards
Obsolete - please see ShEx Semantics
Operational Semantics
Simplified abstract syntax
We use the following simplified abstract syntax:
Rule ::= ArcRule(NameClass,ValueClass)
| AndRule(Rule,Rule)
| OrRule(Rule,Rule)
| OneOrMode(Rule)
| Action(Rule,Action)
| NoRule
Notice that:
Option(Rule) = OrRule(Rule,NoRule)
ZeroOrMore(Rule) = OrRule(OneOrMore(Rule),NoRule)
RDF representation
The operational semantics matches infers a typing for a resource in an RDF graph.
We represent RDF graphs as sets of RDF triples, where an RDF triple is (subj,pred,obj) such that
subj is a URI or a BNode, pred is a URI and obj is a URI, BNode or Literal.
For our purposes, an RDF graph has the following operations:
{} = An empty graph
{t} = Singleton graph with triple t
t :: g = The graph that results of adding triple t to graph g
g1 union g2 = Union of graphs g1 and g2
g.triplesAround(iri) = Selects the triples that contain 'iri' as subject or as object
Operational semantics
The semantics of shape expressions consits of assigning shape typings to
nodes in an RDF graph. A shape typing is a map from RDF nodes (iri's or bNodes) to sets of Labels. We define the following operations on shape typings:
{} = empty shape typing
iri -> label :: typing = the result of assigning iri to label in typing
t1 ++ t2 = combination of typings t1 and t2
Match Shape
matchShape(ctx,iri,shape) returns the typing that results of matching a shape iri with the shape expression shape. It has the following definition:
matchShape
|
g.triplesAround(iri)=ts matchRule(ctx,ts,shape.rule) = t
|
matchShape(ctx,iri,shape) = iri -> shape.label :: t
|
Match Rule
matchRule(ctx,g,r) returns the typing that results of matching the graph g with the rule r in the context ctx. The definition of matchRule has the following rules:
AndRule
|
matchRule(ctx,g1,r2)=t1 matchRule(ctx,g2,r2)=t2
|
matchRule(ctx, g1 union g2, And(r1,r2)) = t1 ++ t2
|
OrRule1
|
matchRule(ctx,g,r1) = t
|
matchRule(ctx, g, OrRule(r1,r2)) = t
|
OrRule2
|
matchRule(ctx,g,r2) = t
|
matchRule(ctx, g, OrRule(r1,r2)) = t
|
NoRule
|
empty
|
matchRule(ctx, {}, NoRule)) = {}
|
OneOrMore1
|
matchRule(ctx,g,r) = t
|
matchRule(ctx, g, OneOrMore(r)) = t
|
OneOrMore2
|
matchRule(ctx,g1,r) = t1 matchRule(ctx,g2,OneOrMore(r)) = t2
|
matchRule(ctx, g1 union g2, OneOrMore(r)) = t1 ++ t2
|
Arc
|
matchName(ctx,triple.pred,n) matchValue(ctx,triple.obj,v) = t
|
matchRule(ctx, {triple}, Arc(n,v)) = t
|
matchName
matchName(ctx,pred,n) matches predicate pred with nameClass n in context ctx. It returns a boolean.
NameTerm
|
pred = t
|
matchName(ctx, pred, NameTerm(t))
|
NameAny
|
not(matchStems(excl,pred))
|
matchName(ctx, pred, NameAny(excl))
|
NameStem
|
matchStem(s,pred)
|
matchName(ctx, pred, NameStem(s))
|
where
matchStem(stem,iri) is true is iri has stem stem
matchStems(stems,iri) is true is iri has a stem one of the set of stems stems
matchValue
matchValue(ctx,obj,v) matches object obj with valueClass v in context ctx. It returns a typing
ValueType
|
obj.type = type
|
matchValue(ctx, obj, ValueType(type)) = {}
|
ValueSet
|
set.contains(obj)
|
matchValue(ctx, obj, ValueSet(set)) = {}
|
ValueReference
|
matchShape(ctx,obj,ctx.getShape(label)) = t
|
matchValue(ctx, obj, ValueReference(label)) = t
|
ValueAny
|
not(matchStems(excl,obj))
|
matchValue(ctx, obj, ValueAny(excl)) = {}
|
ValueStem
|
matchStem(s,obj)
|
matchValue(ctx, obj, ValueStem(s)) = {}
|
matchType
matchType(obj,type) returns true if object obj matches the type type. Notice that obj can be resource, bNode or literal.