Converting Graph Patterns

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.

In summary, the steps are applied as follows:

• Expand syntax forms for IRIs, literals and triple patterns.
• Translate property path expressions
• Convert some property path patterns to triples
• Collect the FILTERs in the group
• Translate Basic Graph Patterns
• Translate the remaining graph patterns in the group
• Add in Filters
• Simplify the algebra expression

We write

translate(graph pattern)

for the algorthm described here to translate graph patterns.

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:

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

This is illustrated by two non-normative test cases:

• Simplification applied after all transformations or not at all.
• Simplification applied during transformation.

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

Expand Syntax Forms

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

Collect FILTER Elements

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.

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

Let FS := empty set

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

The set of filter expressions FS is used later.

Translate Property Path Expressions

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.

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.

Notes:

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

We introduce the following symbols:

• link
• inv
• alt
• seq
• ZeroOrMorePath
• OneOrMorePath
• ZeroOrOnePath
• NPS (for NegatedPropertySet)

Syntax Form (path)	Algebra (path)
iri	link(iri)
^path	inv(path)
!(:iri1|...|:irin)	NPS({:iri1 ... :irin})
!(^:iri1|...|^:irin)	inv(NPS({:iri1 ... :irin}))
!(:iri1|...|:irii|^:irii+1|...|^:irim)	alt(NPS({:iri1 ...:irii}),     inv(NPS({:irii+1, ..., :irim})) )
path1 / path2	seq(path1, path2)
path1 | path2	alt(path1, path2)
path*	ZeroOrMorePath(path)
path+	OneOrMorePath(path)
path?	ZeroOrOnePath(path)

Translate Property Path Patterns

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.

Notes:

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

Algebra (path)	Translation
X link(iri) Y	X iri Y
X inv(iri) Y	Y iri X
X seq(P, Q) Y	X P ?V . ?V Q P
X P Y	Path(X, P, Y)

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

?s :p/:q ?o

?s :p ?_V .

?_V :q ?o

?s :p* ?o

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

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

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

?_V rdf:first ?member

Translate Basic Graph Patterns

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

Translate Graph Patterns

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

If the form is GroupOrUnionGraphPattern

Let A := undefined

For each element G in the GroupOrUnionGraphPattern
    If A is undefined
        A := Translate(G)
    Else
        A := Union(A, Translate(G))
    End

The result is A

If the form is GraphGraphPattern

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

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

If the form is GroupGraphPattern:

Let FS := the empty set
Let G := the empty pattern, a basic graph pattern which is the empty set.

For each element E in the GroupGraphPattern

    If E is of the form OPTIONAL{P} 
        Let A := Translate(P)
        If A is of the form Filter(F, A2)
            G := LeftJoin(G, A2, F)
        Else 
            G := LeftJoin(G, A, true)
            End
        End

    If E is of the form MINUS{P}
        G := Minus(G, Translate(P))
        End

    If E is of the form BIND(expr AS var)
        G := Extend(G, var, expr)
        End

    If E is any other form 
        Let A := Translate(E)
        G := Join(G, A)
        End

   End

The result is G.

If the form is InlineData

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

data is formed by forming a solution mapping from the variable in the corresponding position in list of variables (or single variable), omitting a binding if the BindingValue is the word UNDEF.

If the form is SubSelect

The result is ToMultiset(Translate(SubSelect))

Filters of Group

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

If FS is not empty
    Let G := output of preceding step
    Let X := Conjunction of expressions in FS
    G := Filter(X, G)
    End

Simplification step

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:

Replace join(Z, A) by A
Replace join(A, Z) by A