a , ; "

Converting Graph Patterns

\n\n

This section describes the process for translating a SPARQL graph pattern into a SPARQL algebra expression. This process is applied to the group graph pattern (the unit between {...} delimiters) forming the WHERE clause of a query, and recursively to each syntactic element within the group graph pattern. The result of the translation is a SPARQL algebra expression.

\n

In summary, the steps are applied as follows:

\n\n

We write

\n
\n

translate(graph pattern)

\n
\n

for the algorthm described here to translate graph patterns.

\n

The working group notes that in SPARQL 1.0, the point at which the simplification step is applied leads to ambiguous transformation of queries involving a doubly nested filter and pattern in an optional:

\n
OPTIONAL { { ... FILTER ( ... ?x ... ) } }..\n
\n

This is illustrated by two non-normative test cases:

\n\n

Applying the simpification step after all the translation of graph patterns is the preferred reading.

"^^ ; ; "Converting Graph Patterns" . a ; "
Translate Graph Patterns
\n\n

Next, we translate each remaining graph pattern form, recursively applying the translation process.

\n
\n

If the form is GroupOrUnionGraphPattern

\n
\n
Let A := undefined\n\nFor each element G in the GroupOrUnionGraphPattern\n    If A is undefined\n        A := Translate(G)\n    Else\n        A := Union(A, Translate(G))\n    End\n\nThe result is A\n\n
\n
\n

If the form is GraphGraphPattern

\n
\n
If the form is GRAPH IRI GroupGraphPattern\n    The result is Graph(IRI, Translate(GroupGraphPattern))\n
\n
If the form is GRAPH Var GroupGraphPattern\n    The result is Graph(Var, Translate(GroupGraphPattern))\n
\n
\n

If the form is GroupGraphPattern:

\n
\n
Let FS := the empty set\nLet G := the empty pattern, a basic graph pattern which is the empty set.\n\nFor each element E in the GroupGraphPattern\n\n    If E is of the form OPTIONAL{P} \n        Let A := Translate(P)\n        If A is of the form Filter(F, A2)\n            G := LeftJoin(G, A2, F)\n        Else \n            G := LeftJoin(G, A, true)\n            End\n        End\n\n    If E is of the form MINUS{P}\n        G := Minus(G, Translate(P))\n        End\n\n    If E is of the form BIND(expr AS var)\n        G := Extend(G, var, expr)\n        End\n\n    If E is any other form \n        Let A := Translate(E)\n        G := Join(G, A)\n        End\n\n   End\n\nThe result is G.\n\n
\n
\n

If the form is InlineData

\n
\n
The result is a multiset of solution mappings 'data'.\n
\n
\n

data is formed by forming a solution mapping\nfrom the variable in the corresponding position in list of\nvariables (or single variable), omitting a binding if the\nBindingValue is the word\nUNDEF.

\n

If the form is SubSelect

\n
\n
The result is ToMultiset(Translate(SubSelect))\n
"^^ ; , ; . a ; "
Simplification step
\n\n

Some groups of one graph pattern become join(Z, A), where Z is the empty basic graph pattern (which is the empty set). These can be replaced by A. The empty graph pattern Z is the identity for join:

\n
Replace join(Z, A) by A\nReplace join(A, Z) by A\n
"^^ ; . a ; "
Translate Basic Graph Patterns
\n\n

After translating property paths, any adjacent triple patterns are collected together to form a basic graph pattern BGP(triples).

"^^ ; . a ; "
Filters of Group
\n\n

After the group has been translated, the filter expressions are added so they wil apply to the whole of the rest of the group:

\n
If FS is not empty\n    Let G := output of preceding step\n    Let X := Conjunction of expressions in FS\n    G := Filter(X, G)\n    End\n
"^^ ; . a ; ; ; ; ; ; ; ; ; ; "2023-07-10T15:57:03.357Z"^^ ; "Converting Graph Patterns" ; ; ; . a ; "
Translate Property Path Expressions
\n\n

The following table gives the translation of property paths expressions from SPARQL syntax to terms in the SPARQL algebra. This applies to all elements of a property path expression recursively.

\n

The next step after this one translates certain forms to triple patterns, and these are converted later to basic graph patterns by adjacency (without intervening group pattern delimiters { and }) or other syntax forms. Overall, SPARQL syntax property paths of just an IRI become triple patterns and these are aggregated into basic graph patterns.

\n

Notes:

\n
    \n
  • The order of forms IRI and ^IRI in negated property sets is not relevant.
    • \n
\n

We introduce the following symbols:

\n
    \n
  • link
    • \n
  • inv
    • \n
  • alt
    • \n
  • seq
    • \n
  • ZeroOrMorePath
    • \n
  • OneOrMorePath
    • \n
  • ZeroOrOnePath
    • \n
  • NPS (for NegatedPropertySet)
    • \n
\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
Syntax Form (path)Algebra (path)
\n iri\n \n link(iri)\n
\n ^path\n \n inv(path)\n
\n !(:iri1|...|:irin)\n \n NPS({:iri1 ... :irin})\n
\n !(^:iri1|...|^:irin)\n \n inv(NPS({:iri1 ... :irin}))\n
\n !(:iri1|...|:irii|^:irii+1|...|^:irim) \n alt(NPS({:iri1 ...:irii}),

    inv(NPS({:irii+1, ..., :irim})) )\n
\n path1 / path2\n \n seq(path1, path2)\n
\n path1 | path2\n \n alt(path1, path2)\n
\n path*\n \n ZeroOrMorePath(path)\n
\n path+\n \n OneOrMorePath(path)\n
\n path?\n \n ZeroOrOnePath(path)\n
"^^ ; ; . a ; "
Translate Property Path Patterns
\n\n

The previous step translated property path expressions. This step translates property path patterns, which are a subject end point, property path expression and object end point, into triple patterns or wraps in a general algebra operation for path evaluation.

\n

Notes:

\n
    \n
  • X and Y are RDF terms or variables.
    • \n
  • ?V is a fresh variable.
    • \n
  • P and Q are path expressions.
    • \n
  • These are only applied to property path patterns, not within property path expressions.
    • \n
  • Translations earlier in the table are applied in preference to the last translation.
    • \n
  • The final translation simply wraps any remaining property path expression to use a common form Path(...).
    • \n
\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
Algebra (path)Translation
\n X link(iri) Y\n \n X iri Y\n
\n X inv(iri) Y\n \n Y iri X\n
\n X seq(P, Q) Y\n \n X P ?V . ?V Q P\n
\n X P Y\n \n Path(X, P, Y)\n
\n\n

Examples of the whole path translation process (?_V is a fresh variable):

\n

?s :p/:q ?o

\n

?s :p ?_V .

\n

?_V :q ?o

\n

?s :p* ?o

\n

Path(?s, ZeroOrMorePath(link(:p)), ?o)

\n

:list rdf:rest*/rdf:first ?member

\n

Path(:list, ZeroOrMorePath(link(rdf:rest)), ?_V) .

\n

?_V rdf:first ?member

"^^ ; , ; . a ; "
Expand Syntax Forms
\n\n

Expand abbreviations for IRIs and triple patterns given in section 4.

"^^ ; ; . a ; "
Collect FILTER Elements
\n\n

FILTER expressions apply to the whole group graph pattern in which they appear. The algebra operators to perform filtering are added to the group after translation of each group element. We collect the filters together here and remove them from group, then apply them to the whole translated group graph pattern.

\n

In this step, we also translate graph patterns within FILTER expressions EXISTS and NOT EXISTS.

\n
Let FS := empty set\n\nFor each form FILTER(expr) in the group graph pattern:\n    In expr, replace NOT EXISTS{P} with fn:not([exists(translate(P)))](../../#defn_evalExists) \n    In expr, replace EXISTS{P} with [exists(translate(P))](../../#defn_evalExists)\n    FS := FS ∪ {expr}\n    End\n
\n

The set of filter expressions FS is used later.

"^^ ; , ; .