Negated property sets enable you to formulate a query like, for example: "give me back two resources x and y which are related in any direction via some property, but not via foaf:knows". In SPARQL 1.1, this would look like:
SELECT ?x ?y
WHERE {
?x !(foaf:knows|^foaf:knows) ?y .
}
The current SPARQL 1.1 draft defines a new abstract symbol for supporting negated property sets, called NegatedPropertySet. The SPARQL algebra, in turn, maps this abstract symbol directly to a new algebraic operator, so the algebra is extended with an additional operator in order to support negated property sets, and it also gives a specific evaluation semantics for this new operator.
However, although perhaps useful in terms of brevity, it is in fact not necessary to thus extend the algebra. Negated property sets do not actually introduce additional expressivity to the language (in contrast to, for example, arbitrary-length property paths): the above query could have been formulated in SPARQL 1.0:
SELECT ?x ?y
WHERE {
{ ?x ?p1 ?y . FILTER (?p1 != foaf:knows) }
UNION
{ ?y ?p2 ?x . FILTER (?p2 != foaf:knows) }
}
This simple fact makes it possible to implement negated property sets without having to extend Sesame's query model with an additional algebra operator. The advantage of this is that all of Sesame's existing query optimizing/rewriting/evaluation strategies can immediately handle negated property sets, without having to be 'recalibrated' or indeed extended to take a complex additional operator into account.
So, the SPARQL parser processes a negated property set and translates it to the necessary collection of Joins, Filter comparisons and Unions. The algorithm is roughly as follows:
let NPS be a negated property set with elements e_1...e_n.
let s be the subject variable of the NPS.
let ap be the (anonymous) predicate variable of the NPS.
let O be the set of object variables of the NPS.
let F and F_i be two sets of filter conditions.
let p(e) be the predicate IRI of e.
for each e in NPS :
create a filter condition f: p(e) != ap .
if e is inverted: add f to F_i, otherwise add f to F .
let J be a Join on basic graph patterns.
if F is not empty:
for each o in O :
add BGP(s, ap, o) to J .
let I be a Join on basic graph patterns.
if F_i is not empty:
for each o in O :
add BGP(o, ap, s) to I .
if I and J are both not empty:
return Union(Filter(J, F), Filter(I, F_i)) .
else if I is not empty :
return Filter(I, F_i).
else if J is not empty :
return Filter(J, F).
The end result of applying this algorithm to the example SPARQL 1.1 query we saw above would be the following (slightly adapted for readability) Sesame query algebra expression:
Projection({x, y},
Union(
Filter(StatementPattern(y, ap, x), Compare(!=, ap, foaf:knows)),
Filter(StatementPattern(x, ap, y), Compare(!=, ap, foaf:knows))
)
)
Short and sweet. Of course, it gets less short and sweet when using more complex property sets, or property sets in combination with other property path features, but the algorithm caters to that. Such more complex expression just result in a larger set of unions and joins.
