Property Path Patterns

\n\n

This section defines the evaluation of property path patterns. A property path pattern is a subject endpoint (an RDF term or a variable), a property path express and an object endpoint. The translation of property path expressions converts some forms to other SPARQL expressions, such as converting property paths of length one to triple patterns, which in turn are combined into basic graph patterns. This leaves property path operators ZeroOrOnePath, ZeroOrMorePath, OneOrMorePath and NegatedPropertySets and also path expressions contained within these operators.

\n

All remaining property path expressions are present in the algebra in the form Path(X, path, Y) for endpoints X and Y. For example: syntax(:p/:q)* is a ZeroOrMorePath expression involving a sequence property path becoming the algebra expession ZeroOrMorePath(seq(link(:p), link(:q))).

\n

Notation

\n

Write

\n

eval(Path(X, PP, Y))\n

\n

for the evaluation of the property path patterns. This produces a multiset of solution mappings μ, each solution mapping having a binding for variables used (each of X and Y can be a variable). Some operators only produce a set of solution mappings.

\n

Write

\n

Var(x

\n

1, x

\n

2, ..., x

\n

n) = { x

\n

i | i in 1...n and x

\n

i is a variable }

\n

for the variables in x1, x2, ...,\nxn.

\n

Write

\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n

\n x:term\n	when x is an RDF term
\n x:var\n	when x is a variable
\n x:path\n	when x is a path expression

\n\n

All evaluation is carried out by matching the active graph at that point in the overall query evaluation. We omit explicitly including the active graph in each definition for clarity.

\n

Definition: Evaluation of Predicate Property\nPath

\n

Let Path(X, link(iri), Y) be an predicate inverse property path pattern, using some IRI iri.

\n

\n

eval(Path(X, link(iri), Y)) =

\n

\n

evaluation of basic graph pattern {X iri Y}

\n

If both X and Y are variables, this is the same as:

\n

eval(Path(X:var, link(iri), Y:var)) = { (X, xn) (Y, yn) | xn and yn are RDF terms and triple (xn iri yn) is in the active graph }

\n

If X is a variable and Y an RDF term:

\n

eval(Path(X:var, link(iri), Y:term)) = { (X, xn) | xn is an RDF term and triple (xn iri Y) is in the active graph }

\n

If X is an RDF term and Y is a variable:

\n

eval(Path(X:term, link(iri), Y:var)) = { (Y, yn) | yn is an RDF term and triple (X iri yn) is in the active graph }

\n

If both X and Y are RDF terms:

\n

eval(Path(X:term, link(iri), Y:term)) = { μ

\n

0 } if triple (X iri Y) is in the active graph = { { } } = Ω

\n

0 eval(Path(X:term, link(iri), Y:term)) = { } if triple (X iri Y) is not in the active graph

\n

Informally, evaluating a Predicate Property Path is the same as executing a subquery SELECT * { X P Y } at that point in the query evaluation.

\n

Definition: Evaluation of Inverse Property\nPath

\n

Let P be a property path expression, then:

\n

\n

eval(Path(X, inv(P), Y)) = eval(Path(Y, P, X))\n

\n

Definition: Evaluation of Sequence Property\nPath

\n

Let P and Q be property path expressions. Let V be a fresh variable.

\n

\n

A = Join( eval(Path(X, P, V)), eval(Path(V, Q, Y)) )\n

\n

eval(Path(X, seq(P,Q), Y)) = Project(A, Var(X,Y))\n

\n

Informally, this is the same as:

\n

SELECT * { X P _:a . _:a Q Y }\n

\n

using the fact that a blank node _:a acts like a variable (under simple entailment) except it does not appear in the results from SELECT *.

\n

Definition: Evaluation of Alternative Property\nPath

\n

Let P and Q be property path expressions.

\n

\n

eval(Path(X, alt(P,Q), Y)) = Union(eval(Path(X, P, Y)), eval(Path(X, Q, Y)))\n

\n

Informally, this is the same as:

\n

SELECT * { { X P Y } UNION { X Q Y } }\n

\n

Definition: Node set\nof a graph

\n

The node set of a graph G, nodes(G), is:

\n

nodes(G) = { n | n is an RDF term that is used as a subject or object of a triple of G}

\n

Definition: Evaluation of ZeroOrOnePath

\n

eval(Path(X:term, ZeroOrOnePath(P), Y:var)) = { (Y, yn) | yn = X or {(Y, yn)} in eval(Path(X,P,Y)) }\n

\n

eval(Path(X:var, ZeroOrOnePath(P), Y:term)) = { (X, xn) | xn = Y or {(X, xn)} in eval(Path(X,P,Y)) }\n

\n

eval(Path(X:term, ZeroOrOnePath(P), Y:term)) = \n    { {} } if X = Y or eval(Path(X,P,Y)) is not empty\n    { } othewise\n

\n

eval(Path(X:var, ZeroOrOnePath(P), Y:var)) = \n    { (X, xn) (Y, yn) | either (yn in nodes(G) and xn = yn) or {(X,xn), (Y,yn)} in eval(Path(X,P,Y)) }\n

\n

We define an auxillary function, ALP, used in the definitions of ZeroOrMorePath and OneOrMorePath. Note that the algorithm given here serves to specify the feature. An implementation is free to implement evaluation by any method that produces the same results for the query overall. The ZeroOrMorePath and OneOrMorePath forms return matches based on distinct nodes connected by the path.

\n

The matching algorithm is based on following all paths, and detecting when a graph node (subject or object), has been already visited on the path.

\n

Informally, this algorithm attempts to extend the multiset of results by one application of path at each step, noting which nodes it has visited for this particular path. If a node has been visited for the path under consideration, it is not a candidate for another step.

\n

Definition: Function ALP

\n

Let eval(x:term, path) be the evaluation of 'path', starting at RDF term x, \n                       and returning a multiset of RDF terms reached \n                       by repeated matches of path.\n\nALP(x:term, path) = \n    Let V = empty multiset\n    ALP(x:term, path, V)\n    return is V\n\n# V is the set of nodes visited\n\nALP(x:term, path, V:set of RDF terms) =\n    if ( x in V ) return \n    add x to V\n    X = eval(x,path) \n    For n:term in X\n        ALP(n, path, V)\n        End\n

\n

Definition: Evaluation of ZeroOrMorePath

\n

eval(Path(X:term, ZeroOrMorePath(path), vy:var)) =\n    { { (vy, n) } | n in ALP(X, path) }\n\neval(Path(vx:var, ZeroOrMorePath(path), vy:var)) =\n    { { (vx, t), (vy, n) } |  t in nodes(G), (vy, n) in eval(Path(t, ZeroOrMorePath(path), vy)) }\n\neval(Path(vx:var, ZeroOrMorePath(path), y:term)) = \n    eval(Path(y:term, ZeroOrMorePath(inv(path)), vx:var))\n\neval(Path(x:term, ZeroOrMorePath(path), y:term)) = \n    { { } } if { (vy:var,y) } in eval(Path(x, ZeroOrMorePath(path) vy)\n    { } otherwise\n\n

\n

Definition: Evaluation of OneOrMorePath

\n

eval(Path(X, OneOrMorePath(path), Y))

\n

# For OneOrMorePath, we take one step of the path then start\n# recording nodes for results.\n\neval(Path(x:term, OneOrMorePath(path), vy:var)) =\n    Let X = eval(x, path)\n    Let V = the empty multiset\n    For n in X\n        ALP(n, path, V)\n        End\n    result is V\n\neval(Path(vx:var, OneOrMorePath(path), vy:var)) =\n   { { (vx, t), (vy, n) } |  t in nodes(G), (vy, n) in eval(Path(t, OneOrMorePath(path), vy)) }\n\neval(Path(vx:var, OneOrMorePath(path), y:term)) =\n   eval(Path(y:term, OneOrMorePath(inv(path)), vx))\n\neval(Path(x:term, OneOrMorePath(path), y:term)) =\n    { { } } if { (vy:var, y) } in eval(Path(x, OneOrMorePath(path), vy))\n    { } otherwise\n\n

\n

Definition: Evaluation of\nNegatedPropertySet

\n

Write μ' as the extension of a solution mapping:\nμ'(μ,x) = μ(x)   if x is a variable\nμ'(μ,t) = t   if t is a RDF term\n\n

\n

Let x and y be variables or RDF terms, and S a set of IRIs:\n\neval(Path(x, NPS(S), y)) = { μ | ∃ triple(μ'(μ,x), p, μ'(μ,y)) in G, such that the IRI of p ∉ S }\n\n

D : a dataset\nD(G) : D a dataset with active graph G (the one patterns match against)\nD[i] : The graph with IRI i in dataset D\nP, P1, P2 : graph patterns\nL : a solution sequence\nF : an expression\n

eval(D(G), BGP) = multiset of solution mappings\n

eval(D(G), Path(X, path, Y)) = multiset of solution mappings\n

eval(D(G), Filter(F, P)) = Filter(F, eval(D(G),P), D(G))\n

eval(D(G), Join(P1, P2)) = Join(eval(D(G), P1), eval(D(G), P2))\n

eval(D(G), LeftJoin(P1, P2, F)) = LeftJoin(eval(D(G), P1), eval(D(G), P2), F)\n

eval(D(G), Union(P1,P2)) = Union(eval(D(G), P1), eval(D(G), P2))\n

if IRI is a graph name in D\neval(D(G), Graph(IRI,P)) = eval(D(D[IRI]), P)\n

if IRI is not a graph name in D\neval(D(G), Graph(IRI,P)) = the empty multiset\n

eval(D(G), Graph(var,P)) =\n     Let R be the empty multiset\n     foreach IRI i in D\n        R := Union(R, Join( eval(D(D[i]), P) , Ω(?var->i) )\n     the result is R\n\n

eval(D(G), Extend(P, var, expr)) = Extend(eval(D(G), P), var, expr)\n

eval(D(G), ToList(P)) = ToList(eval(D(G), P))\n

eval(D(G), Distinct(L)) = Distinct(eval(D(G), L))\n\n

eval(D(G), Reduced(L)) = Reduced(eval(D(G), L))\n\n

eval(D(G), Project(L, vars)) = Project(eval(D(G), L), vars)\n\n

eval(D(G), OrderBy(L, condition)) = OrderBy(eval(D(G), L), condition)\n\n

eval(D(G), ToMultiSet(L)) = ToMultiSet(eval(D), M))\n

eval(D(G), Slice(L, start, length)) = Slice(eval(D(G), L), start, length)\n