The SPARQL 1.1 Query Language [1] permits patterns inside FILTER expressions using the EXISTS construct, speci ed by using substitution. Substitution destroys some of the aspects of SPARQL that make it suitable as a data access language. As well, substitution causes problems in the SPARQL algebra and produces counterintuitive results. Fixing the problems with EXISTS is best done with a completely di erent de nition that does not use substitution at all. EXISTS is used inside FILTER constructs to determine whether a pattern matches or does not match. EXISTS can be used to nd people who do not have any names, as in this example from the SPARQL speci cation [1, x8.1.1]: SELECT ?person WHERE f ?person rdf:type foaf:Person . [1] FILTER NOT EXISTS f ?person foaf:name ?name g g Any SPARQL pattern can be used in an EXISTS, including subqueries, as in a query to nd people who know someone who knows more than 100 others: SELECT ?person WHERE f ?person foaf:knows ?friend . FILTER EXISTS f SELECT ?friend WHERE f ?friend foaf:knows ?y . g GROUP BY ?friend HAVING ( COUNT(*) > 100 ) g g De nition The de nition of EXISTS in SPARQL starts with a translation to the SPARQL algebra [1, x18.2.2.2], replacing EXISTSfPg with exists(translate( P)). The function exists is described as \exists(pattern) is a function that returns true [i ] the pattern evaluates to a non-empty solution sequence." [1, x18.5] The formal de nition of exists uses substitution into its argument Substitute Let be a solution mapping. substitute(pattern, ) = the pattern formed by replacing every occurrence of a variable v in pattern by (v) for each v in dom( ). [1, x18.6] Evaluation of Exists Let be the current solution mapping for a lter and P a graph pattern: The value exists(P), given D(G) is true if and only if eval(D(G), substitute( P, )) is a non-empty sequence. [1, x18.6] Counterintuitive Results Blank nodes in the graph being queried often produce counterintuitive results with EXISTS. In Query [1] the substitution is performed for every node in the graph that has an rdf:type link to foaf:Person. If one of these nodes is a blank node, say :Bill, the evaluation ends up matching :Bill foaf:name ?name against the graph. As :Bill is a blank node, it acts like a variable and can itself be mapped. As a consequence, no answers will be returned from Query [1] for the graph ex:John rdf:type foaf:Person ; foaf:name "John" . [G] :Bill rdf:type foaf:Person .
This counterintuitive result is particularly pernicious as it can occur any time a FILTER variable is used to query the graph inside an EXISTS.
MINUS is also problematic inside EXISTS. One might expect the result of SELECT ?x WHERE f BIND ( :b AS ?x )
FILTER EXISTS f ?x :p :b . MINUS f ?x :p :b g g g to be empty because any solution mapping on the left side of the MINUS is eliminated by the same mapping from right side. However, substitution replaces ?x with :b so the two sides don't share a variable and then, because of its de nition in SPARQL, the MINUS does not remove any solution mappings.
Substitution also interferes with SPARQL constructs that act like variable bindings. One might expect that
SELECT ?x WHERE f ?x :p :b . [
FILTER EXISTS f ?x :p :b . f SELECT ( :d AS ?x ) WHERE f g g g g has no solutions except for ?x mapped to :d because otherwise solutions from ?x :p :b, i.e., with ?x mapped to something other than :d cannot be joined to solutions from SELECT ( :d AS ?x ) WHERE f g. However, the substitution replaces ?x throughout with :d so the \variable" that comes out of the subquery is not ?x but instead is whatever ?x was mapped to.
Implementations of SPARQL don't produce all these counterintuitive results,
instead diverging from the speci cation, but some do produce some of them.
Semantic Anomalies The substitution for EXISTS does not distinguish
between the di erent uses of variables in SPARQL constructs. It substitutes in
triples, as it needs to, and in expressions, which it also needs to, but it also
substitutes in other places. In Query [
This semantic anomaly happens in SELECT clauses, as above, but also in BIND constructs like
SELECT ?x WHERE f BIND ( :b AS ?x ) BIND ( :b AS ?y )
FILTER EXISTS f BIND ( :j AS ?x ) BIND ( :k AS ?y ) g g and in VALUES constructs [4, errata-query-10]. In each case mappings are created that do not conform with the de nition of solution mappings in SPARQL.
Other semantic anomalies can also arise, as in
SELECT ?x WHERE f :b :p ?x . FILTER EXISTS f FILTER BOUND(?x) g g where the BOUND function is applied to a non-variable, counter to its de nition in SPARQL.
Some of these anomalous situations have further problems, as in SELECT ?x WHERE f BIND ( :b AS ?x ) BIND ( :b AS ?y )
FILTER EXISTS f f SELECT ( :d AS ?x ) WHERE f g g
f SELECT ( :e AS ?y ) WHERE f g g g g Here both ?x and ?y end up being substituted as :b so the join between the results from the subqueries ends up being empty, which is counterintuitive as well as being semantically anomalous.
We have not found a SPARQL implementation that reports these semantic anomalies. Either they silently allow illegal internal constructs or they silently do something di erent from the speci cation. Bottom-up Evaluation SPARQL is supposedly designed so that queries can be evaluated \bottom-up [and] subqueries are evaluated logically rst, and the results are projected up to the outer query." [1, x12] However, EXISTS is at odds with this design because EXISTS substitution creates altered subqueries that did not exist before the substitution. Because of this, for some queries the results of an evaluation based on substitution will di er dramatically from those produced by bottom-up evaluation, as exhibited by:
SELECT ?x WHERE f ?x :b ?y .
FILTER EXISTS f SELECT ?z WHERE f ?z :f ?y . g g g
The problem is particularly acute with uses of variables that would not contribute to solution mappings, such as the nested use of ?y in the following. In this query, the results prescribed by substitution not only di er from bottom-up results, but they are also strongly counterintuitive, as in the query below where no results will be returned because ?y is replaced, even though this variable does not contribute mappings to the results returned from the inner query.
SELECT ?x WHERE f ?x :p ?y .
FILTER EXISTS f SELECT ?x WHERE f ?x :p ?y . g
GROUP BY ?x HAVING ( COUNT(*) > 1 ) g g
There is a suggested erratum that these variables should not be subject to
substitution [4, errata-query-8]. Di erent implementations of SPARQL produce
di erent answers for these queries, as noticed by Hernndez et al [
Fixing the De nition To summarize, EXISTS produces counterintuitive
results, generates semantic anomalies, hinders bottom-up evaluation, is not
implemented as speci ed, and has divergent implementations. The problem lies rmly
with substitute, which navely replaces variables with values even in places where
this substitution produces unde ned algebra constructs or changes their
meaning. Making a more nuanced version of substitute that does not substitute in these
problematic spots is not possible without extensive changes to the SPARQL
algebra, because such approaches would leave variables incorrectly unconstrained
as, for example, in Query [
Given that a xed version of substitute is not possible, is another kind of
de nition of EXISTS a solution? Yes, a de nition of EXISTS based on solution
mappings is possible. The core of this de nition basically moves the FILTER
solution mapping to the beginning of the argument to EXISTS. For the solution
mapping f(?person, :Bill)g in [
The technical details of this x to EXISTS are as follows: 1. Add a new construct, Initial, to the SPARQL syntax and algebra. Initial will be used to set up the initial multiset of solution mappings inside an EXISTS. It will work much like VALUES except that it will transfer solution mappings through the EXISTS instead of setting up a constant solution mapping. 2. When collecting FILTER elements replace EXISTSfpatterng in the lter expression with exists(Initial(t),translate(fInitial(t) pattern'g)) where t is a fresh token, and similarly for NOT EXISTSfpatterng. If pattern is a SubSelect then pattern' is fpatterng otherwise pattern' is just pattern. 3. Translate Initial(t) as itself. 4. Change the de nition of the exists function to:
Let be the current solution mapping for a lter, t a token, and P a graph pattern: The value exists(Initial(t),P) given D(G) is true i eval(D(G),P') is a non-empty multiset of solution bindings, where P' is P with Initial(t) replaced by f g.
This de nition eliminates all the semantic anomalies resulting from EXISTS. It also xes the counterintuitive results above. It corresponds better to how EXISTS behaves in SPARQL implementations. As well, under this de nition all subqueries in SPARQL queries can then be evaluated completely bottom up and independently of anything outside of the subquery. In particular, subqueries inside EXISTS can be evaluated before the solution mappings going into the FILTER are known.
Variants of this de nition are possible, for example, by adding Initial(t) to the beginning of GroupGraphPatterns and not just at the top, that modify the behaviour of EXISTS without reintroducing any semantic anomalies.
Pre-binding [
Pre-binding can be given a formal de nition using the technique proposed here for EXISTS. This version of pre-binding pushes a solution mapping into the query by adding Initial(0) to the WHERE clause as in Point 2 evaluates the resulting query in the same way that EXISTS is evaluated.
The de nition of EXISTS proposed here eliminates the counterintuitive results of SPARQL, avoids producing any semantic anomalies, and makes SPARQL more suitable as a data access language. It is in all ways better than the current substitution de nition.