Negation in SPARQL Renzo Angles1,3 and Claudio Gutierrez2,3 1 Dept. of Computer Science, Universidad de Talca, Chile 2 Dept. of Computer Science, Universidad de Chile, Chile 3 Center for Semantic Web Research Abstract. This paper presents a thorough study of negation in SPARQL. The types of negation supported in SPARQL are identified and their main features discussed. Then, we study the expressive power of the cor- responding negation operators. At this point, we identify a core SPARQL algebra which could be used instead of the W3C SPARQL algebra. Fi- nally, we analyze the negation operators in terms of their compliance with elementary axioms of set theory. 1 Introduction The notion of negation has been largely studied in database query languages, mainly due to their implications in aspects of expressive power and computa- tional complexity [4–6, 12, 16]. There have been proposed several types of nega- tion, and it seems difficult to get agreement about a standard one. Such hetero- geneity comes from intrinsic properties and semantics of each language, features that determine its ability to support specific type(s) of negation(s). The case of SPARQL is no exception. SPARQL 1.0 did not have any ex- plicit 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 filter constraints, by using the Boolean NOT operator; negation as failure, implemented as the combination of an optional graph pattern and the bound operator; difference 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 specifications, 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 different types of nega- tion supported in SPARQL, and discuss their main features. Then, we study the relationships (in terms of expressive power) among the negation operators, first 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 oper- ations 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 difference operator introduced at the level of the SPARQL algebra. With this new difference operator, we show that one can define a core algebra (i.e. projection, selection, join, union and simple difference) which is able to express the W3C SPARQL algebra. We show that this algebra is also able to define 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 SPARQL graph patterns The following definition of SPARQL graph patterns is based on the formalism used in [13], but in agreement with the W3C SPARQL specifications [14, 7]. RDF graphs. Assume two disjoint infinite 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 ) ∈ 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 infinite 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 defined. The empty mapping, denoted µ0 , is the mapping satisfying that dom(µ0 ) = ∅. Given ?X ∈ V and c ∈ T , we use µ(?X) = c to denote the solution mapping variable ?X to term c. Similarly, µ?X→c denotes a mapping µ satisfying that dom(µ) = {?X} and µ(?X) = c. Given a finite set of variables W ⊂ V , the restriction of a mapping µ to W , denoted µ|W , is a mapping µ0 satisfying that dom(µ0 ) = dom(µ) ∩ W and µ0 (?X) = µ(?X) for every ?X ∈ dom(µ) ∩ W . Two mappings µ1 , µ2 are compatible, denoted µ1 ∼ µ2 , when for all ?X ∈ dom(µ1 ) ∩ dom(µ2 ) it satisfies that µ1 (?X) = µ2 (?X), i.e., when µ1 ∪ µ2 is also a mapping. Note that two mappings with disjoint domains are always compatible, and that the empty mapping µ0 is compatible with any other mapping. A selection formula is defined recursively as follows: (i) If ?X, ?Y ∈ V and c ∈ 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 affect our results. ¬(F ) are boolean selection formulas. The evaluation of a selection formula F under a mapping µ, denoted µ(F ), is defined in a three-valued logic with values true (>), false (⊥), and error (ξ). We say that µ satisfies F where µ(F ) = true. The semantics of µ(F ) is defined as follows: – If F is ?X = c and ?X ∈ dom(µ), then µ(F ) = true when µ(?X) = c and µ(F ) = false otherwise. If ?X ∈ / dom(µ) then µ(F ) = error. – If F is ?X =?Y and ?X, ?Y ∈ dom(µ), then µ(F ) = true when µ(?X) = µ(?Y ) and µ(F ) = false otherwise. If either ?X ∈ / dom(µ) or ?Y ∈ / dom(µ) then µ(F ) = error. – If F is bound(?X) and ?X ∈ 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 repre- sented as a set of solution mappings, each one annotated with a positive integer which defines 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 multi- set Ω. In this sense, it applies that card(µ, Ω) = 0 when µ ∈ / Ω. We use Ω0 to de- note the multiset {µ0 } such that card(µ0 , Ω0 ) > 0 (Ω0 is called Sthe join identity). The domain of a solution mapping Ω is defined as dom(Ω) = µ∈Ω dom(µ). W3C SPARQL algebra. Let Ω1 , Ω2 be multisets of mappings, W be a set of vari- ables and F be a selection formula. The W3C SPARQL algebra for multisets of mappings is composed of the operations of projection, selection, join, difference, left-join, union and minus, defined respectively as follows: – πW (Ω1 ) = {µ0 | µ ∈ Ω1 , µ0 = Pµ|W } where card(µ0 , πW (Ω1 )) = µ0 =µ|W card(µ, Ω1 ) – σF (Ω1 ) = {µ ∈ Ω1 | µ(F ) = true} where card(µ, σF (Ω1 )) = card(µ, Ω1 ) – Ω1 o n Ω2 = {µ = (µ1 ∪ µ2 ) P| µ1 ∈ Ω1 , µ2 ∈ Ω2 , µ1 ∼ µ2 } where card(µ, Ω1 o n Ω2 ) = µ=(µ1 ∪µ2 ) card(µ1 , Ω1 ) × card(µ2 , Ω2 ) – Ω1 \F Ω2 = {µ1 ∈ Ω1 | ∀µ2 ∈ Ω2 , (µ1  µ2 )∨(µ1 ∼ µ2 ∧(µ1 ∪µ2 )(F ) 6= true)} where card(µ1 , Ω1 \F Ω2 ) = card(µ1 , Ω1 ) – Ω1 ∪ Ω2 = {µ | µ ∈ Ω1 ∨ µ ∈ Ω2 } where card(µ, Ω1 ∪ Ω2 ) = card(µ, Ω1 ) + card(µ, Ω2 ) – Ω1 − Ω2 = {µ1 ∈ Ω1 | ∀µ2 ∈ Ω2 , µ1  µ2 ∨ dom(µ1 ) ∩ dom(µ2 ) = ∅} where card(µ1 , Ω1 − Ω2 ) = card(µ1 , Ω1 ) – Ω1 qyo n Ω2 ) ∪ (Ω1 \F Ω2 ) n F Ω2 = σF (Ω1 o where card(µ, Ω1 qyo n F Ω2 ) = card(µ, σF (Ω1 on Ω2 )) + card(µ, Ω1 \F Ω2 ) Syntax of graph patterns. A SPARQL graph pattern is defined recursively as fol- lows: A tuple from (I∪L∪V )×(I∪V )×(I∪L∪V ) is a graph pattern called a triple pattern. 6 If P1 and P2 are graph patterns then (P1 AND P2 ), (P1 UNION P2 ), (P1 OPT P2 ), (P1 MINUS P2 ) and (P1 NOT-EXISTS P2 ) are graph patterns. If P1 is a graph pattern and C is a filter constraint (as defined below) then (P1 FILTER C) is a graph pattern. A filter constraint is defined recursively as follows: (i) If ?X, ?Y ∈ V and c ∈ I ∪L then (?X = c), (?X =?Y ) and bound(?X) are atomic filter constraints; (ii) If C1 and C2 are filter constraints then (!C1 ), (C1 || C2 ) and (C1 && C2 ) are complex filter constraints. Given a filter constraint C, we denote by f (C) the selection formula obtained from C. Note that there exists a simple and direct translation from filter 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 definition, we denote by µ(P ) the graph pattern obtained by the recursive substitution of variables in every triple pattern and filter constraint occurring in the graph pattern P according to µ. Semantics of SPARQL graph patterns. The evaluation of a SPARQL graph pat- tern P over an RDF graph G is defined 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 filter constraint. The evaluation of a graph pattern P over a graph G is defined recursively as follows: 1. If P is a triple pattern t, then JP KG = {µ | dom(µ) = var(t) ∧ µ(t) ∈ G} where each mapping µ has cardinality 1. 2. J(P1 AND P2 )KG = JP1 KG o n JP2 KG 3. If P is (P1 OPT P2 ) then (a) if P2 is (P3 FILTER C) then JP KG = JP1 KG qyo n C JP3 KG (b) else JP KG = JP1 KG qyo n (true) JP2 KG 4. J(P1 MINUS P2 )KG = JP1 KG − JP2 KG 5. J(P1 NOT-EXISTS P2 )KG = {µ | µ ∈ JP1 KG ∧ Jµ(P2 )KG = ∅} 6. J(P1 UNION P2 )KG = JP1 KG ∪ JP2 KG 7. J(P1 FILTER C)KG = σf (C) (JP1 KG ) 3 Types of negation in SPARQL We can distinguish four types of negation in SPARQL: negation of filter con- straints, 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 filter constraints. The most basic type of negation in SPARQL is the one allowed in filter 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 µ satisfies the filter constraint (!C), i.e. µ does not satisfy the constraint C. The negation of filter 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 specification remarks that the negation of graph patterns can be implemented as a combination of an optional graph pattern and a filter 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 intro- duce the operator DIFF as an explicit way of expressing it. It is very important to note that the DIFF operator is not defined in SPARQL. Definition 1 (DIFF). Let P1 and P2 be graph patterns. The DIFF operator is defined as J(P1 DIFF P2 )K = {µ1 ∈ JP1 K | ∀µ2 ∈ JP2 K, µ1  µ2 }. Negation by MINUS. SPARQL 1.1 introduced the MINUS operator as an ex- plicit way of expressing the negation (or difference) of graph patterns. Note that DIFF and MINUS have similar definitions. The difference is given by the restric- tion 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 different results for DIFF and MINUS. Basically, if P1 and P2 do not have vari- ables in common then J(P1 DIFF P2 )K = ∅ whereas J(P1 MINUS P2 )K = JP1 K. Note that both, DIFF and MINUS resemble the EXCEPT operator of SQL[11]. Considering that EXCEPT makes reference to the difference of two relations (ta- bles), we say that DIFF and MINUS express the difference of two graph patterns. Negation by NOT-EXISTS. Another type of negation defined 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 JP1 K, 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 Expressive Power In this section we study the expressive power of the negation operators defined 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 lan- guage. Recall that the W3C SPARQL algebra, defined 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 difference”. Definition 2 (Simple difference). The simple difference between two solution mappings, Ω1 and Ω2 , is defined as Ω1 \ Ω2 = {µ1 ∈ Ω1 | ∀µ2 ∈ Ω2 , µ1  µ2 } where card(µ1 , Ω1 \ Ω2 ) = card(µ1 , Ω1 ). Definition 3 (Core SPARQL algebra). The core SPARQL algebra is com- posed by the operations of projection, selection, join, union and simple difference. Next, we will show that the core SPARQL algebra contains the W3C SPARQL algebra. Specifically, we will show that the operators of difference, left-join and minus (of the W3C SPARQL algebra) can be simulated with the simple differ- ence operator (of the core SPARQL algebra). Lemma 1. The difference 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))). ?x∈X 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 fixed in this version. We thank them for this notice. null. Additionally, we define the multisets Ω θ = σ∆(dom(Ω),θ) (Ω o n θ(Ω)) and Ω ⊥ = ⊥dom(θ(Ω)) (Ω θ ). Given two multisets of solution mappings Ω1 and Ω2 , we have that Ω1 \F Ω2 = πdom(Ω1 ) (Ω1⊥ \ (πdom(θ(Ω1 )) (σF (Ω1⊥ o n Ω2 )))). Lemma 2. The left-join operator (of the W3C SPARQL algebra) is expressible in the core SPARQL algebra. Proof. By definition, Ω1 qyo n Ω2 ) ∪ (Ω1 \F Ω2 ), and by previous n F Ω2 = σF (Ω1 o lemma \F 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 0 (Ω1 − Ω2 ) = πdom(Ω1 ) (Ω1⊥ \ (⊥dom(θ(Ω1 )) (πdom(θ(Ω1 )) (σF (Ω1θ o n Ω2θ ))))) where F is the selection formula _ (θ(?x) = θ0 (?x)). ?x∈dom(Ω1 ) Based on Lemmas 1, 2 and 3, we can present our main result about the expressive power of the core SPARQL algebra: 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 difference operator. A core fragment with negation Let us redefine the DIFF operator by using the simple difference operator of the core algebra as J(P1 DIFF P2 )K = JP1 K\JP2 K. Assume that SPARQLDIFF is the language defined (recursively) by graph pat- terns 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 = JP1 K qyo n C JP3 K; (ii) else, JP K = JP1 K qyo n (true) JP2 K. 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 “un- safe” variables. The set of safe variables in a graph pattern P , denoted svar(P ), is defined 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 . Definition 4 (SPARQLNEX NEX safe ). Define SPARQLsafe 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 ∈ 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 SPARQLNEX safe are ex- pressible in SPARQLDIFF . Proof. Following the definition of SPARQLNEX safe , we have that for any graph pat- tern (P1 NOT-EXISTS P2 ) it satisfies that the domain of JP2 K 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 SPARQLNEX safe . 5 Properties of the SPARQL negation operators In this section we study the behavior of the negation operators in terms of ele- mentary equivalences found in set theory. Specifically, we consider the following axioms concerning set-theoretic differences [15]: (a) A \ A ≡ ∅ (g) A \ (A ∩ B) ≡ A \ B (b) A \ ∅ ≡ A (h) A ∩ (A \ B) ≡ A \ B (c) ∅ \ A ≡ ∅ (i) (A \ B) ∪ B ≡ A ∪ B (d) A \ (A \ (A \ B)) ≡ A \ B (j) (A ∪ B) \ B ≡ A \ B (e) (A ∩ B) \ B ≡ ∅ (k) A \ (B ∩ C) ≡ (A \ B) ∪ (A \ C) (f ) (A \ B) ∩ B ≡ ∅ (l) A \ (B ∪ C) ≡ (A \ B) ∩ (A \ C) In order to evaluate the set-based equivalences in the context of SPARQL, we need to assume two conditions: (1) As a general rule, a set-based operator requires two “objects” with the same structure (e.g. two tables with the same schema). Such requirement is implicitly satisfied in SPARQL thanks to the def- inition of solution mappings as partial functions. (2) SPARQL does not provide an explicit operator for intersecting two graph patterns P1 and P2 . Note however, that a graph pattern (P1 AND P2 ) resembles the intersection operation (under set-semantics) when JP1 K and JP2 K have the same domain of variables. Given the above two conditions, we can apply a direct translation from a set-theoretic equivalence to a graph pattern equivalence. Specifically, the set- difference operator will be mapped to a SPARQL negation operator (DIFF, MI- NUS or NOT-EXISTS), the set-intersection operator will be mapped to AND, and the set-union operator will be replaced by UNION. Considering the spe- cific 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 JP1 K = ∅, JP2 K = {µ0 }, 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 five cases for equivalences (a)-(j) and one hundred twenty five cases for equivalences (k) and (l). The differences between set and bag semantics were specially considered for equivalences (h), (i), (k) and (l). DIFF satisfies most equivalences with exception of (h), (i), (k) and (l). Equiv- alence (h) presents five 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 satisfied 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 satisfied. 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 be- havior 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 defined. In fact, the heterogeneity of the operators is a motivation to study their intrinsic properties and to try the definition 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 Conclusions In this paper we presented a systematic analysis of the types of negation sup- ported in SPARQL 1.0 and SPARQL 1.1. After introducing the standard rela- tional 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 define 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 identified (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 Millen- nium Nucleus Center for Semantic Web Research under Grant NC120004. We also thank the anonymous referees for their helpful feedback. References 1. Angles, R., Gutierrez, C.: SQL Nested Queries in SPARQL. In: Proc. of the 4th Alberto Mendelzon Workshop on Foundations of Data Management (2010) 2. Angles, R., Gutierrez, C.: Subqueries in SPARQL. In: Proc. of the 5th Alberto Mendelzon Workshop on Foundations of Data Management (2011) 3. Angles, R., Gutierrez, C.: Negation in SPARQL. Talk at 8th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW) (2014) 4. Bárány, V., Cate, B., Segoufin, L.: Guarded negation. Journal of the ACM 62(3), 22:1–22:26 (2015) 5. Bidoit, N.: Negation in rule-based database languages: A survey. Theoretical Com- puter Science 78(1), 3–83 (1991) 6. Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing 9(3), 365–386 (1991) 7. Harris, S., Seaborne, A.: SPARQL 1.1 Query Language - W3C Recommendation. http://www.w3.org/TR/2013/REC-sparql11-query-20130321/ (March 21 2013) 8. Hogan, A., Arenas, M., Mallea, A., Polleres, A.: Everything you always wanted to know about blank nodes. Journal of Web Semantics 27(1) (2014) 9. Kaminski, M., Kostylev, E.V., Cuenca Grau, B.: Semantics and Expressive Power of Subqueries and Aggregates in SPARQL 1.1. In: Proc. of the International Con- ference on World Wide Web. pp. 227–238 (2016) 10. Kim, W.: On optimizing an SQL-like nested query. ACM Transactions on Database Systems (TODS) 7(3), 443–469 (1982) 11. Melton, J., Simon, A.R.: SQL:1999 Understanding Relational Language Compo- nents. Morgan Kaufmann (May 2001) 12. Naqvi, S.A.: Negation as failure for first-order queries. In: Proc. of the Symposium on Principles of Database Systems. pp. 114–122. ACM (1986) 13. Pérez, J., Arenas, M., Gutierrez, C.: Semantics and Complexity of SPARQL. ACM Transactions on Database Systems (TODS) 34(3), 1–45 (2009) 14. Prud’hommeaux, E., Seaborne, A.: SPARQL Query Language for RDF. W3C Recommendation. http://www.w3.org/TR/2008/REC-115-sparql-query- 20080115/ (January 15 2008) 15. Suppes, P.: Axiomatic Set Theory. The University Series in Undergraduate Math- ematics, D. Van Nostrand Company, Inc. (1960) 16. Wagner, G.: A database needs two kinds of negation. In: Proc. of the Symposium on Mathematical Fundamentals of Database and Knowledge Base Systems. pp. 357–371 (1991)