This paper presents a thorough study of negation in SPARQL. The types of negation supported in SPARQL are identi ed and their main features discussed. Then, we study the expressive power of the corresponding negation operators. At this point, we identify a core SPARQL algebra which could be used instead of the W3C SPARQL algebra. Finally, we analyze the negation operators in terms of their compliance with elementary axioms of set theory.
The notion of negation has been largely studied in database query languages, mainly due to their implications in aspects of expressive power and computational complexity [4{6, 12, 16]. There have been proposed several types of negation, and it seems di cult to get agreement about a standard one. Such heterogeneity comes from intrinsic properties and semantics of each language, features that determine its ability to support speci c type(s) of negation(s).
The case of SPARQL is no exception. SPARQL 1.0 did not have any explicit form of negation in its syntax, but could simulate negation by failure. For the next version, SPARQL 1.1, the incorporation of negation generated a lot of debate. As result, SPARQL 1.1 provides four types of negation: negation of lter constraints, by using the Boolean NOT operator; negation as failure, implemented as the combination of an optional graph pattern and the bound operator; di erence of graph patterns, expressed by the MINUS operator; and existential negation of graph patterns, expressed by the NOT-EXISTS operator. The main positive and negative aspects of these types of negation are remarked in the SPARQL speci cations, and more detailed discussions are available in the records of the SPARQL working group4. The goal of this paper is to conduct a formal study about negation in SPARQL.
First, we formalize the syntax and semantics of the di erent types of negation supported in SPARQL, and discuss their main features. Then, we study the relationships (in terms of expressive power) among the negation operators, rst at the level of the SPARQL algebra, and subsequently at the level of SPARQL graph patterns. Finally, we present a case-by-case analysis of the negation operations with respect to their compliance with elementary axioms of set theory. 4 https://www.w3.org/2009/sparql/wiki/Design:Negation
It would be good to have a simple version of negation operators that conform to a known intuition. This is the other main contribution of this paper. First we introduce the DIFF operator as another way of expressing the negation of graph patterns (DIFF is the SPARQL version of the EXCEPT operator of SQL). The semantics of DIFF is based on a simple di erence operator introduced at the level of the SPARQL algebra. With this new di erence operator, we show that one can de ne a core algebra (i.e. projection, selection, join, union and simple di erence) which is able to express the W3C SPARQL algebra. We show that this algebra is also able to de ne the SPARQL operators, thus it can be considered a sort of \core" SPARQL algebra. Additionally, we show that the DIFF operator behaves well regarding its compliance with axioms of set theory.
For the sake of space we avoid extended proofs of our results. We refer the reader to the technical report available at http://arxiv.org/abs/1603.06053. 2
The following de nition of SPARQL graph patterns is based on the formalism used in [13], but in agreement with the W3C SPARQL speci cations [14, 7]. RDF graphs. Assume two disjoint in nite sets I and L, called IRIs and literals respectively. An RDF term is an element in the set T = I [ L5. An RDF triple is a tuple (v1; v2; v3) 2 I I T where v1 is the subject, v2 the predicate and v3 the object. An RDF Graph (just graph from now on) is a set of RDF triples. The union of graphs, G1 [ G2, is the set theoretical union of their sets of triples. Additionally, assume the existence of an in nite set V of variables disjoint from T . We will use var( ) to denote the set of variables occurring in the structure .
A solution mapping (or just mapping from now on) is a partial function
: V ! T where the domain of , dom( ), is the subset of V where is de ned.
The empty mapping, denoted 0, is the mapping satisfying that dom( 0) = ;.
Given ?X 2 V and c 2 T , we use (?X) = c to denote the solution mapping
variable ?X to term c. Similarly, ?X!c denotes a mapping satisfying that
dom( ) = f?Xg and (?X) = c. Given a nite set of variables W V , the
restriction of a mapping to W , denoted jW , is a mapping 0 satisfying that
dom( 0) = dom( ) \ W and 0(?X) = (?X) for every ?X 2 dom( ) \ W . Two
mappings 1; 2 are compatible, denoted 1 2, when for all ?X 2 dom(
A selection formula is de ned recursively as follows: (i) If ?X; ?Y 2 V and c 2 I [ L then (?X = c), (?X =?Y ) and bound(?X) are atomic selection formulas; (ii) If F and F 0 are selection formulas then (F ^ F 0), (F _ F 0) and 5 In addition to I and L, RDF and SPARQL consider a domain of anonymous resources called blank nodes. The occurrence of blank nodes introduces several issues that are not discussed in this paper. Based on the results presented in [8], we avoid the use of blank nodes assuming that their absence does not largely a ect our results. :(F ) are boolean selection formulas. The evaluation of a selection formula F under a mapping , denoted (F ), is de ned in a three-valued logic with values true (>), false (?), and error ( ). We say that satis es F where (F ) = true. The semantics of (F ) is de ned as follows: { If F is ?X = c and ?X 2 dom( ), then (F ) = true when (?X) = c and (F ) = false otherwise. If ?X 2= dom( ) then (F ) = error. { If F is ?X =?Y and ?X; ?Y 2 dom( ), then (F ) = true when (?X) = (?Y ) and (F ) = false otherwise. If either ?X 2= dom( ) or ?Y 2= dom( ) then (F ) = error. { If F is bound(?X) and ?X 2 dom( ) then (F ) = true else (F ) = false. { If F is (F ^ F 0) then > ^ > = >, > ^ ? = ?, > ^ = , ? ^ > = ?, ? ^ ? = ?, ? ^ = ?, ^ > = , ^ ? = ?, ^ = . { If F is (F _ F 0) then > _ > = >, > _ ? = >, > _ = >, ? _ > = >, ? _ ? = ?, ? _ = , _ > = >, _ ? = , _ = . { If F is :(F ) then :> = ?, :? = >, : = .
A multiset (or bag ) of solution mappings is an unordered collection in which each solution mapping may appear more than once. A multiset will be represented as a set of solution mappings, each one annotated with a positive integer which de nes its multiplicity (i.e. its cardinality). We use the symbol to denote a multiset and card( ; ) to denote the cardinality of the mapping in the multiset . In this sense, it applies that card( ; ) = 0 when 2= . We use 0 to denote the multiset f 0g such that card( 0; 0) > 0 ( 0 is called the join identity). The domain of a solution mapping is de ned as dom( ) = S dom( ). 2 W3C SPARQL algebra. Let 1; 2 be multisets of mappings, W be a set of variables and F be a selection formula. The W3C SPARQL algebra for multisets of mappings is composed of the operations of projection, selection, join, di erence, left-join, union and minus, de ned respectively as follows: 2g
card( 2; 2) 2 ^( 1 [ 2)(F ) 6= true)g
W (
F (
1 on 2 = f = ( 1 [ 2) j 1 2 1; 2 2 2; 1 where card( ; 1 on 2) = P =( 1[ 2) card( 1; 1)
1 nF 2 = f 1 2 1 j 8 2 2 2; (
1 [ 2 = f j 2 where card( ; 1 [
1 2 = f 1 2 1 j 8 2 2 2; 1 where card( 1; 1 2) = card( 1; 1)
1qyon F 2 = F ( 1 on 2) [ ( 1 nF 2)
where card( ; 1qyon F 2) = card( ; F ( 1 on
1 _ 2 2g
2) = card( ; 1) + card( ; 2)
2 _ dom(
A lter constraint is de ned recursively as follows: (i) If ?X; ?Y 2 V and c 2 I [ L then (?X = c), (?X =?Y ) and bound(?X) are atomic lter constraints ; (ii) If C1 and C2 are lter constraints then (!C1), (C1 jj C2) and (C1 && C2) are complex lter constraints. Given a lter constraint C, we denote by f (C) the selection formula obtained from C. Note that there exists a simple and direct translation from lter constraints to selection formulas and viceversa.
Given a triple pattern t and a mapping such that var(t) dom( ), we denote by (t) the triple obtained by replacing the variables in t according to . Overloading the above de nition, we denote by (P ) the graph pattern obtained by the recursive substitution of variables in every triple pattern and lter constraint occurring in the graph pattern P according to . Semantics of SPARQL graph patterns. The evaluation of a SPARQL graph pattern P over an RDF graph G is de ned as a function JP KG (or JP K where G is clear from the context) which returns a multiset of solution mappings. Let P1; P2; P3 be graph patterns and C be a lter constraint. The evaluation of a graph pattern P over a graph G is de ned recursively as follows: 1. If P is a triple pattern t, then JP KG = f j dom( ) = var(t) ^ where each mapping has cardinality 1. (t) 2 Gg 2. J(P1 AND P2)KG = JP1KG on JP2KG 3. If P is (P1 OPT P2) then (a) if P2 is (P3 FILTER C) then JP KG = JP1KGqyon C JP3KG (b) else JP KG = JP1KGqyon (true)JP2KG 4. J(P1 MINUS P2)KG = JP1KG JP2KG 5. J(P1 NOT-EXISTS P2)KG = f j 2 JP1KG ^ J (P2)KG = ;g 6. J(P1 UNION P2)KG = JP1KG [ JP2KG 7. J(P1 FILTER C)KG = f(C)(JP1KG) 3
We can distinguish four types of negation in SPARQL: negation of lter constraints, negation as failure, negation by MINUS and negation by NOT-EXISTS. The main features of these types of negation will be discussed in this section. 6 We assume that any triple pattern contains at least one variable.
Negation of lter constraints. The most basic type of negation in SPARQL is the one allowed in lter graph patterns by including constraints of the form (!C). Following the semantics of SPARQL, a graph pattern (P FILTER(!C)), returns the mappings in JP K such that satis es the lter constraint (!C), i.e.
does not satisfy the constraint C. The negation of lter constraints is a feature well established in SPARQL and does not deserve major discussion. In the rest of the paper we concentrate our interest on the negation of graph patterns. Negation as failure. SPARQL 1.0 does not include an operator to express the negation of graph patterns. In an intent of patching this issue, the SPARQL speci cation remarks that the negation of graph patterns can be implemented as a combination of an optional graph pattern and a lter constraint containing the bound operator (see [14], Sec. 11.4.1). This style of negation, called negation as failure in logic programming, can be illustrated as a graph pattern P of the form ((P1 OPT P2) FILTER(! bound(?X))) where ?X is a variable of P2 not occurring in P1. Note that, the evaluation of P returns the mappings of J(P1 OPT P2)K satisfying that variable ?X is unbounded, i.e. ?X does not match P2. In other words, P returns \the solution mappings of P1 that are not compatible with the solutions mappings of P2". Unfortunately, there are some issues with this approach [3]. A general solution is included in our technical report.
In order to facilitate the study of negation by failure in SPARQL, we introduce the operator DIFF as an explicit way of expressing it. It is very important to note that the DIFF operator is not de ned in SPARQL.
De nition 1 (DIFF). Let P1 and P2 be graph patterns. The DIFF operator is de ned as J(P1 DIFF P2)K = f 1 2 JP1K j 8 2 2 JP2K; 1 2g.
Negation by MINUS. SPARQL 1.1 introduced the MINUS operator as an explicit way of expressing the negation (or di erence) of graph patterns. Note that DIFF and MINUS have similar de nitions. The di erence is given by the restriction about disjoint mappings included by the MINUS operator. Such restriction, named Antijoin Restriction inside the SPARQL working group7, was introduced to avoid solutions with vacuously compatible mappings. Such restriction causes di erent results for DIFF and MINUS. Basically, if P1 and P2 do not have variables in common then J(P1 DIFF P2)K = ; whereas J(P1 MINUS P2)K = JP1K.
Note that both, DIFF and MINUS resemble the EXCEPT operator of SQL[11]. Considering that EXCEPT makes reference to the di erence of two relations (tables), we say that DIFF and MINUS express the di erence of two graph patterns. Negation by NOT-EXISTS. Another type of negation de ned in SPARQL 1.1 is given by the NOT-EXISTS operator. The main feature of this type of negation is the possible occurrence of correlation. Given a graph pattern P = (P1 NOT-EXISTS P2), we will say that P1 and P2 are correlated when there 7 http://lists.w3.org/Archives/Public/public-rdf-dawg/2009JulSep/0030.html exist variables occurring in both P1 and P2; such variables are called correlated variables. In this case, the evaluation of P is attained by replacing variables in P2 with the corresponding values given by the current mapping of JP1K, and testing whether the evaluation of the graph pattern (P2) returns no solutions. This way of evaluating correlated queries is based on the nested iteration method [10] of SQL. The correlation of variables in NOT-EXISTS introduces several issues that have been studied in the context of subqueries in SPARQL [1, 2]. Some of these issues are discussed in Section 4. 4
In this section we study the expressive power of the negation operators de ned in the above section, i.e. DIFF, MINUS and NOT-EXISTS.
The core SPARQL algebra Let us introduce a \core" algebra for SPARQL which is able to express all the high-level operators of the W3C SPARQL language. Recall that the W3C SPARQL algebra, de ned in Section 2, is composed by the operators of projection, selection, join, union, left-join and minus. Our core algebra is based on a new operator called \simple di erence". De nition 2 (Simple di erence). The simple di erence between two solution mappings, 1 and 2, is de ned as 1 n 2 = f 1 2 1 j 8 2 2 2; 1 2g where card( 1; 1 n 2) = card( 1; 1).
De nition 3 (Core SPARQL algebra). The core SPARQL algebra is composed by the operations of projection, selection, join, union and simple di erence.
Next, we will show that the core SPARQL algebra contains the W3C SPARQL algebra. Speci cally, we will show that the operators of di erence, left-join and minus (of the W3C SPARQL algebra) can be simulated with the simple di erence operator (of the core SPARQL algebra).
Lemma 1. The di erence operator (of the W3C SPARQL algebra) is expressible in the core SPARQL algebra.8 Proof. Let be a function for fresh renaming of variables. Given a set of variables X, we use (X; ) to represent the expression ^ (?x = (?x) _ (: bound(?x) ^ : bound( (?x))): ?x2X Given a multiset and a set of variables X, the function ?X ( ) returns a copy of where all unbound slots have been substituted by a free constant, e.g. 8 When preparing the camera ready version, we received a notice from E. Kostylev and R. Kontchakov about their paper \On Expressibility of Non-Monotone Operators in SPARQL" presented at KR 2016. They also pointed to some bugs in our proof of Lemma 1 which were xed in this version. We thank them for this notice. null. Additionally, we de ne the multisets ? = ?dom( ( ))( ).
Given two multisets of solution mappings = (dom( ); )( on
( )) and
1 and
2, we have that
1 nF
2 =
dom(
Proof. By de nition, 1qyon F 2 = F ( 1 on 2) [ ( 1 nF lemma nF can be simulated in core SPARQL algebra.
Lemma 3. The minus operator (of the W3C SPARQL algebra) is expressible in the core SPARQL algebra.
Proof. Let and 0 be functions for fresh renaming of variables. Following the notations of the proof of Lemma 1, we have that Theorem 1. The W3C SPARQL algebra is expressible with the core SPARQL algebra.
This result implies that the W3C SPARQL algebra could be implemented by a subset of the original operators (projection, selection, join and union), plus the simple di erence operator.
A core fragment with negation Let us rede ne the DIFF operator by using the simple di erence operator of the core algebra as J(P1 DIFF P2)K = JP1KnJP2K. Assume that SPARQLDIFF is the language de ned (recursively) by graph patterns of the form (P AND P 0), (P UNION P 0), (P DIFF P 0) and (P FILTER C). Lemma 4. The OPT operator is expressible in SPARQLDIFF.
Proof. Given a graph pattern P of the form (P1 OPT P2), we have two cases: (i) if P2 is (P3 FILTER C) then JP K = JP1Kqyon C JP3K; (ii) else, JP K = JP1Kqyon (true)JP2K.
For case (i), we can design a graph pattern based on the simulations described in Lemmas 1 and 2. For case (ii), we have that ((P1 OPT P2) FILTER(true)) can be rewritten as ((P1 AND P2) UNION(P1 DIFF P2)).
Lemma 5. The MINUS operator is expressible in SPARQLDIFF. Proof. We have that (P1 MINUS P2) can be rewritten to a DIFF-based graph pattern following the simulation described in the proof of Lemma 3. NOT-EXISTS vs DIFF Intuitively, one can assume that any graph pattern P = (P1 NOT-EXISTS P2) can be expressed by using P 0 = (P1 DIFF P2) or (P1 EXCEPT P2). This is for example argued by Kaminski et.al [9] (Lemma 3) but the translation given there does not work. Thus it would be interesting to identify a subset of NOT-EXISTS graph patterns that can be expressed by using the DIFF operator. To do this, we will introduce the notion of \safe" and \unsafe" variables. The set of safe variables in a graph pattern P , denoted svar(P ), is de ned recursively as follows: If P is a triple pattern, then svar(P ) = var(P ); If P is (P1 AND P2) then svar(P ) = svar(P1) [ svar(P2); If P is (P1 UNION P2) or (P1 OPT P2) then svar(P ) = svar(P1) \ svar(P2); If P is (P1 FILTER C), (P1 MINUS P2), (P1 NOT-EXISTS P2) or (P1 DIFF P2) then svar(P ) = svar(P1). Therefore, a variable occurring in svar(P ) is called a safe variable, otherwise it is considered unsafe in P .
De nition 4 (SPARQLsNaEfeX). De ne SPARQLsNaEfeX as the fragment of SPARQL graph patterns satisfying that the occurrence of a subpattern (P NOT-EXISTS P 0) implies that, for every correlated variable ?X between P and P 0, it holds that ?X 2 svar(P 0).
Note that, SPARQLNEX does not allow graph patterns of the form (P1 NOT-EXISTS(P2 NOT-EXISTS P3)) where P3 contains correlated variables occurring in P1 but not occurring in P2.
Lemma 6. The NOT-EXISTS graph patterns allowed in SPARQLsNaEfeX are expressible in SPARQLDIFF.
Proof. Following the de nition of SPARQLsNaEfeX, we have that for any graph pattern (P1 NOT-EXISTS P2) it satis es that the domain of JP2K contains all the correlated variables between P1 and P2. Given such condition, it is easy to see that J(P1 DIFF P2)K returns the same solutions as J(P1 NOT-EXISTS P2)K.
Based on Lemmas 4, 5 and 6, we can present our main result about the expressive power of the DIFF operator and SPARQLDIFF.
Theorem 2. SPARQLDIFF contains SPARQLsNaEfeX. 5
In this section we study the behavior of the negation operators in terms of elementary equivalences found in set theory. Speci cally, we consider the following axioms concerning set-theoretic di erences [15]: (a) A n A ; (b) A n ; A (c) ; n A ; (d) A n (A n (A n B)) (e) (A \ B) n B ; (f ) (A n B) \ B ;
A n B (g) A n (A \ B) (h) A \ (A n B) (i) (A n B) [ B (j) (A [ B) n B (k) A n (B \ C) (l) A n (B [ C)
A n B A n B A [ B A n B (A n B) [ (A n C) (A n B) \ (A n C)
In order to evaluate the set-based equivalences in the context of SPARQL,
we need to assume two conditions: (
Given the above two conditions, we can apply a direct translation from a set-theoretic equivalence to a graph pattern equivalence. Speci cally, the setdi erence operator will be mapped to a SPARQL negation operator (DIFF, MINUS or NOT-EXISTS), the set-intersection operator will be mapped to AND, and the set-union operator will be replaced by UNION. Considering the speci c features of NOT-EXISTS (i.e. correlation of variables), we will restrict our analysis to DIFF and MINUS.
Let P1, P2, P3, P4 and P5 be graph patterns satisfying that JP1K = ;, JP2K = f 0g, var(P3) = var(P4) and var(P3) \ var(P5) = ;. By combining the above four graph patterns, we conducted a case-by-case analysis consisting of twenty ve cases for equivalences (a)-(j) and one hundred twenty ve cases for equivalences (k) and (l). The di erences between set and bag semantics were specially considered for equivalences (h), (i), (k) and (l).
DIFF satis es most equivalences with exception of (h), (i), (k) and (l). Equivalence (h) presents ve cases which are not valid under bag semantics, although they are valid under set semantics. A similar condition occurs with ten and seven cases for equivalences (k) and (l) respectively. Additionally, we found ten cases which are not satis ed by equivalence (i). MINUS does not satisfy equivalences (e) to (l). We found several cases where equivalences (e), (f), (g), (j) and (k) are not satis ed. Similarly, there exist multiple cases where equivalences (h), (i) and (l) do not apply under bag semantics, but works for set semantics. We would like to remark that the \odd results" presented by the MINUS operator arise because its restriction about disjoint solution mappings.
In summary, we have that each negation operator presents a particular behavior for the axioms studied here. Although none of them was able to satisfy all the axioms, we think that it does not mean that they are badly de ned. In fact, the heterogeneity of the operators is a motivation to study their intrinsic properties and to try the de nition of a set of desired properties for negation in SPARQL. The details about our case-by-case analysis are included in the technical report. 6
In this paper we presented a systematic analysis of the types of negation supported in SPARQL 1.0 and SPARQL 1.1. After introducing the standard relational negation (the DIFF operator) we were able to build a core and intuitive algebra (the same as the standard relational algebra) in SPARQL and prove that it is able to de ne the graph pattern operators.
We think that having a clear understanding of the operators of negation of SPARQL helps both, developers of databases, and users of the query language. We also think that the core language we identi ed (which is precisely the well known and intuitive relational algebra) is a much easier way to express queries for database practitioners, who learn from the beginning SQL, which now with this new algebra, can be found in the world of SPARQL.
Acknowledgements. R. Angles and C. Gutierrez are founded by the Millennium Nucleus Center for Semantic Web Research under Grant NC120004. We also thank the anonymous referees for their helpful feedback.