Semantics of SPARQL under OWL 2 Entailment Regimes

Abstract

We study the semantics of SPARQL queries with optional matching features under entailment regimes. We argue that the normative semantics may lead to answers that are in con ict with the intuitive meaning of optional matching, where unbound variables naturally represent unknown information. We propose an extension of the SPARQL algebra that addresses these issues and is compatible with any entailment regime satisfying the minimal requirements given in the normative speci cation. We then study the complexity of query evaluation and show that our extension comes at no cost for regimes with an entailment relation of reasonable complexity. Finally, we show that our semantics preserves the known properties of optional matching that are commonly exploited for static analysis and optimisation.

Introduction

SPARQL became the standard language for querying RDF in 2008 [ 1 ]. Since then, the theoretical properties of SPARQL have been the subject of intensive research e orts and are by now relatively well-understood [2{7]. At the same time, SPARQL has become a core technology in practice, and most RDF-based applications rely on SPARQL endpoints for query formulation and processing.

The functionality of many such applications is enhanced by OWL 2 ontologies [ 8 ], which are used to provide background knowledge about the application domain, and to enrich query answers with implicit information. A new version of SPARQL, called SPARQL 1.1, was released in 2013 [ 9 ]. This new version captures the capabilities of OWL 2 by means of the so-called entailment regimes [ 10 ]: a exible mechanism for extending SPARQL query answering to the W3C standards layered on top of RDF. A regime speci es which RDF graphs and SPARQL queries are legal (i.e., admissible) for the regime, as well as an entailment relation that unambiguously de nes query answers for all legal queries and graphs.

The semantics of SPARQL under entailment regimes is speci ed for the conjunctive fragment, where queries are represented as basic graph patterns (i.e., sets of RDF triples with variables) and query answers are directly provided by the entailment relation of the regime. Roughly speaking, to check whether a mapping from variables of the query to nodes in the RDF graph is an answer to the query, one rst transforms the query itself into an RDF graph by substituting each variable with the corresponding value, and then checks whether this graph is entailed in the regime by the original data graph [10{12].

When one goes beyond the basic fragment of SPARQL the language becomes considerably more complicated, but the e ect of entailment regimes on the query semantics remains circumscribed to basic graph patterns [ 13, 14 ]. To evaluate a query one must rst evaluate its component basic patterns using the relevant regime and then compose the results by means of the SPARQL algebra operations.

Of particular interest from both a theoretical and a practical perspective is the extension of the basic fragment of SPARQL with the optional matching feature, which is realised in the language by means of the OPTIONAL operator (abbreviated by OPT in this paper). This feature allows the optional information to be added to query answers only when the information is available in the RDF data graph: if the optional part of the query does not match the data, then the relevant variables are left unbounded in query answers.

One of the main motivations behind optional matching in SPARQL is to deal with the \lack of regular, complete structures in RDF graphs" (see [ 9 ] Section 6) and hence with the inherent incompleteness of information in RDF data sources where only partial information about the relevant Web resources is typically available. In this setting, an unbound variable in an answer mapping is naturally interpreted as a \null" value, meaning that there might exist a binding for this variable if we consider other information elsewhere on the Web, but none is currently available in the RDF graph at hand. Another (and slightly di erent) motivation for optional matching was to introduce a mechanism for \not rejecting solutions because some part of the query pattern does not match" [ 1 ]; in this sense, one would naturally expect optional matching to either extend solutions with the optional information, or to leave solutions unchanged. Both readings of optional matching coincide if we focus just on RDF, and they are faithfully captured by the normative semantics. In this paper we argue that they naturally diverge once we consider more sophisticated entailment regimes. Furthermore, the di erences that arise can have a major impact on expected answers.

To make this discussion concrete, let us brie y discuss a simple example of an RDF graph representing the direct train lines between UK cities as well as ferry boat transfers from UK cities to international destinations. Let this graph be exhaustive in its description of rail connections, but much less so in what concerns ferry transfers. We may exploit optional matching to retrieve all direct train connections between cities X and Y, extended with ferry transfers from Y to other cities Z whenever possible. Under the normative semantics of SPARQL we may obtain answers (London; Oxford ; ) and (London; Holyhead ; ) provided the graph has information about direct train lines from London to both Oxford and Holyhead , but no matching can be found in the graph for ferry connections starting from Oxford or Holyhead to other cities. Suppose next that the data graph is extended to a graph corresponding to an OWL 2 ontology in which it is stated that inland cities do not have ferry connections, and that Oxford is an inland city. The ontology establishes a clear distinction between Oxford and Holyhead : whereas the former is inland and cannot have ferry connections, the latter may still well be (and indeed is) a coastal city o ering a number of transfers to international destinations. The normative OWL 2 direct semantics entailment regime, however, does not distinguish between the case of Holyhead (where the information about ferry connections is still unknown) and Oxford (where the information is certain), and both answers would be returned. In this way, the normative semantics adopts the reading of optional matching where the optional information is used to complete (but never discard) query answers. In contrast, under the reading of unbounded variables as placeholders for unknown information, one would naturally expect the answer on Oxford to be ruled out. Indeed, if our goal were to nd rail to ferry transfers starting from London and terminating in Dublin by rst querying this graph and then looking for the missing information elsewhere on the Web, discarding cities like Oxford on the rst stage would signi cantly facilitate our task.

In this paper, we propose an alternative semantics for the OPT operator which adopts the aforementioned reading of optional matching as an incomplete \null". We call our semantics strict, which re ects the fact that it rules out those answers in which unbound variables in the optional part cannot be matched to any consistent extension of the input graph. Our semantics is given as an extension of the SPARQL algebra and hence satis es the expected compositionality properties of algebraic query languages. Furthermore, it is backwards-compatible with the normative semantics for regimes in which all legal graphs are consistent, such as the RDF regime [ 10 ]. We also study the complexity of query evaluation and show that our extension comes at no cost for regimes in which entailment is not harder than query evaluation under normative semantics for the RDF regime. Finally, we show that our semantics preserves the known properties of optional matching that are commonly exploited for static analysis and optimisation.

This paper is an updated version of the work [ 15 ]. 2

SPARQL 1.1 under Entailment Regimes

In this section, we formalise the syntax and normative semantics of a core fragment of SPARQL 1.1 with optional matching under entailment regimes. Our formalisation is based on the normative speci cation documents [9{11] and builds on the well-known foundational works on SPARQL [ 2, 3, 6 ]. 2.1

Syntax

Let I, L, and B be in nite sets of IRIs, literals, and blank nodes, respectively. The set of RDF terms T is I [ L [ B. An RDF triple is a triple (s p o) from

T I T, with s called subject, p predicate, and o object. An (RDF) graph is

a nite set of RDF triples. Assume additionally the existence of a countably in nite set V of variables disjoint from T. A triple pattern is a tuple from (T [ V) (I [ V) (T [ V). A basic graph pattern (BGP) is a nite set of triple patterns. Built-in conditions are conditions of the form bound(?X), ?X = c, and ?X =?Y for ?X; ?Y 2 V and c 2 T, and their Boolean combinations.

Complex graph patterns are constructed from BGPs using a range of available operators that are applicable to graph patterns and built-in conditions. We focus on the AND-OPT-FILTER fragment (i.e., we consider neither union nor projection), which is widely accepted to be the fundamental core of SPARQL [ 2 ]. In this setting, graph patterns are inductively de ned as follows (e.g., see [ 11 ]): 1. every BGP is a graph pattern; 2. if P1 and P2 are graph patterns that share no blank nodes then (P1 AND P2) and (P1 OPT P2) are graph patterns (called AND and OPT patterns); and 3. if P is a graph pattern and R is a built-in condition, then (P FILTER R) is a graph pattern (called FILTER pattern).

In what follows vars(P ) (respectively triples(P )) denotes all the variables from V (respectively all triple patterns) that appear in a graph pattern P .

We conclude with the de nition of a special class of graph patterns with intuitive behaviour [ 2 ]. A graph pattern is well-designed if and only if for each of its OPT subpatterns (P1 OPT P2) the pattern P1 mentions all the variables of P2 which appear outside this subpattern. Note that all graph patterns in the examples of this paper are well-designed. 2.2

Semantics of BGPs under Entailment Regimes

The semantics of graph patterns is de ned in terms of mappings ; that is, partial functions from variables V to terms T. The domain dom( ) of a mapping is the set of variables on which is de ned. The set of triples obtained from a BGP P by replacing each ?X from dom( ) by (?X) is denoted by (P ).

Two mappings 1 and 2 are compatible (written as 1 2) if 1(?X) = 2(?X) for all variables ?X which are in both dom( 1) and dom( 2). If 1 2, then we write 1 [ 2 for the mapping obtained by extending 1 with 2 on variables unde ned in 1. A mapping 1 is subsumed by a mapping 2 (written 1 v 2) i 1 2 and dom( 1) dom( 2). Finally, a set of mappings 1 is subsumed by a set of mappings 2 (written 1 v 2) i for each 1 2 1 there exists 2 2 2 such that 1 v 2.

Based on [ 10 ], an (entailment) regime R is a tuple (R; G; P; C; J K), where 1. R is a set of reserved IRIs from I; 2. G is the set of legal graphs; 3. P is the set of legal BGPs; 4. C is the set of consistent graphs, such that C G; and 5. J K is the query answering function, that takes a graph G from G and a BGP P from P and returns either a set JP KG of mappings such that dom( ) = vars(P ), if P 2 C; or Err, otherwise.

As in most theoretical works on SPARQL [ 2, 3, 6, 16 ], we assume that the query answering function returns a set of mappings, rather than a multiset.

The de nitions of query answering and consistency in a regime are based on an entailment relation [ 10 ], which is also speci ed as part of the regime. We do not model the entailment relation explicitly, but assume two conditions that capture the e ects of any reasonable entailment relation on legality and consistency. All regimes mentioned in the normative speci cation satisfy these properties and in this paper we consider only regimes that do so. (C1) If graphs G, G1 and G2 are legal, and there is h : T ! T, preserving R, such that h(G1 [ G2) G then G1 [ G2 is legal; if, in addition, G is in C then G1 [ G2 is also in C. (C2) If a BGP P is in P then (P ) is in G for any (total) : V ! (T n R), such that (P ) is a graph; if also (P ) is in C then 2 JP K (P ).

Condition (C1) formalises (a weak form of) the monotonicity of legality and consistency: an illegal graph that is a union of legal ones cannot be made legal by identifying and renaming of non-reserved terms or adding triples to it; moreover, a similar property holds for consistency. Condition (C2) guarantees, that \freezing" variables of a legal BGP to non-reserved terms gives us a legal graph, and, moreover, if such a graph is consistent, then the answer of the BGP on this graph contains the mapping corresponding to the \freezing".

The notions introduced in the remainder of this paper are parameterised with a regime R, which is not mentioned explicitly for brevity. 2.3

Normative Semantics under Entailment Regimes

Following [ 2 ], now we show how the query answering function J K extends to complex graph patterns (we refer to [ 2 ] for details). A mapping satis es a built-in condition R, denoted j= R, if one of the following holds: 1. R is bound(?X) and ?X 2 dom( ); or 2. R is ?X = c, ?X 2 dom( ), and (?X) = c; or 3. R is ?X =?Y , ?X 2 dom( ), ?Y 2 dom( ), and (?X) = (?Y ); or 4. R is an evaluating to true Boolean combination of other built-in conditions. The join, di erence, and left outer join of sets of mappings 1, 2 are as follows: 1 on 2 = f 1 [ 2 j 1 2 1 and 2 2 2 such that 1 1 n 2 = f 1 j 1 2 1; there is no 2 2 2 such that 1 1 on 2 = ( 1 on 2) [ ( 1 n 2): 2g; 2g; A graph pattern is legal for a regime R if all the BGPs it contains are legal. The normative query answering function J Kn is inductively de ned for all legal graph patterns P on the base of J K as follows. For graphs G from C we have: 1. if P is a BGP then JP KnG = JP KG; 2. if P is (P1 AND P2) then JP KnG = JP1KnG on JP2KnG; 3. if P is (P1 OPT P2) then JP KPnGKnG==JPf1KnGj on JP2KnG; and 4. if P is (P 0 FILTER R) then J 2 JP 0KnG and j= Rg. If G 62 C then JP KnG = Err for any graph pattern P (which again coincides with JP KG when P is a BGP). Note, that by these de nitions 2 JP KnG implies that dom( ) vars(P ), but this inclusion may be strict if P contains OPT operator.

Two legal patterns P1 and P2 are equivalent (under normative semantics),

denoted by P1 n P2, if JP1KnG = JP2KnG for every RDF graph G 2 G. 3

On Optional Matching Under the Normative Semantics

One of the main motivations for optional matching in SPARQL was to deal with the \lack of regular, complete structures in RDF graphs" [ 9 ]. Indeed, RDF data is loosely structured, and in many applications it is not satisfactory to reject an answer if some relevant information is missing. For example, if we are interested in retrieving the names, emails, and websites of employees, we may not want to discard a partial answer involving the name and email address of an employee merely because the information on the employee's website is not available in the graph. The normative semantics was designed to deal with such situations: the optional information is included in query answers only when the information is available; otherwise, the relevant variables are left unbounded. An unbound variable in an answer is thus a manifestation of inherent incompleteness of RDF data sources, and the missing information is interpreted as unknown.

This natural interpretation of query results, however, no longer holds if the query is evaluated under certain entailment regimes, as we illustrate next by means of examples. In these and all other examples given later on, we focus on the OWL 2 direct semantics regime. In order for an RDF graph to be legal for this regime, it must correspond to an OWL 2 ontology; similarly, legal BGPs must correspond to an extended ontology in which variables are allowed [ 10 ]. Thus, in the examples we express RDF graphs and BGPs in (extended) OWL 2 functional syntax, and use words \ontology" and \graph" interchangeably (we also omit declaration axioms in ontologies and BGPs to avoid clatter). Example 1. Consider the OWL 2 ontology O1 consisting of the axioms

ClassAssertion(InlandCity Oxford ); PropertyAssertion(train London Oxford );

ClassAssertion(CoastalCity Holyhead ); PropertyAssertion(train London Holyhead );

PropertyDomain(ferry CoastalCity );

DisjointClasses(CoastalCity InlandCity ):

Consider also the following graph pattern P1, which we wish to evaluate over O1: PropertyAssertion(train ?X ?Y ) OPT PropertyAssertion(ferry ?Y ?Z): Intuitively, solutions to P1 provide direct train lines from city X to city Y as well as, optionally, the ferry transfers from Y to other cities Z. Under the normative semantics, the BGPs in P1 are evaluated separately. In particular, the optional BGP is evaluated to the empty set, and JP1KnO1 = f 1; 2g, where 1 = f?X 7! London; ?Y 7! Oxford g and 2 = f?X 7! London; ?Y 7! Holyhead g: In both answers, variable ?Z is unbounded and hence we conclude that O1 contains no relevant information about ferry connections starting from Oxford or Holyhead . However, the nature of the lack of such information is fundamentally di erent. On the one hand, the connections from Holyhead (e.g., to Dublin) are missing from O1 just by the incompleteness of the information in the graph, which is usual in (and also a feature of) Semantic Web applications. On the other hand, Oxford cannot have a ferry connection because it is a landlocked city, and hence the information about its (lack of) ferry connections is certain. Thus, the normative semantics cannot distinguish between unknown and non-existent ferry connections. However, if we adhere to the reading of unbounded variables as incomplete information or \nulls", then 1 should not be returned as an answer.

The issues described in this example become even more apparent in cases where the optional part alone cannot be satis ed, as in the following example. Example 2. Consider the ontology O2 with the axioms

ClassAssertion(Person Peter );

DisjointProperties(hasFather hasMother ): Furthermore, consider the following pattern P2: ClassAssertion(Person ?X) OPT (f

PropertyAssertion(hasFather ?X ?Y ); PropertyAssertion(hasMother ?X ?Y )g): The optional BGP does not match to anything, so JP2KnO2 consists of f?X 7! Peter g. However, this BGP is in contradiction with the disjointness axiom: under the OWL 2 regime, no solution to P2 exists for any ontology with this axiom.

As these examples suggest, if we interpret unbound variables in answers to queries with optional parts as an indication of unknown information in the data graph, then the normative semantics may yield counter-intuitive answers. At the core of this issue is the inability of the normative semantics to distinguish between answers in which it is possible to assign values to the missing optional part (a natural re ection of incompleteness in the data), and those where this is impossible (a re ection that the missing information is incompatible with the answer). This distinction is immaterial for regimes without inconsistencies, but it becomes apparent in more sophisticated regimes, such as those based on OWL 2. 4

Semantics of Strict Optional Matching

In this section, we propose our novel semantics for optional matching under regimes. In a nutshell, our semantics addresses the issues described in Section 3 by ruling out those answer mappings where unbound variables in the optional part cannot be matched to any consistent extension of the input graph. Our semantics is therefore strict, in the sense that only answers in which unbound variables are genuine manifestations of incompleteness in the data are returned. 4.1

De nition of Strict Semantics

We start by introducing the notion of a frozen RDF graph for a pattern P and a mapping . Roughly speaking, this graph is obtained by taking all the triple patterns in P and transforming them into RDF triples by applying the extension of where unbounded variables are \frozen" to arbitrary fresh constants. De nition 1. Let R = (R; G; P; C; J K) be an entailment regime. Let P be a legal graph pattern, and let be a mapping from variables V to RDF terms T. Then, the freezing GP of P under is the RDF graph (triples(P )), where is the mapping that extends by assigning each variable in vars(P ), which is not in dom( ), to a globally fresh IRI from I not belonging to R.

The freezing GP depends only on the candidate mapping and the triple patterns occurring in P ; thus, it does not depend either on the speci c operators used in P , or on the RDF graph over which the query pattern is to be evaluated. Example 3. For pattern P1 and mappings 1, 2 from Example 1 the freezings GP11 and GP21 have the following form, for fresh IRIs k and `: fPropertyAssertion(train London Oxford ); PropertyAssertion(ferry Oxford k)g; fPropertyAssertion(train London Holyhead );PropertyAssertion(ferry Holyhead `)g:

Intuitively, the freezing represents the simplest and most general RDF graph over which all the unde ned variables in a given solution mapping could be bounded to concrete values. Thus, if GP together with the input graph G is not a consistent graph for the relevant regime, we can conclude, using condition (C1) of the regime, that the unde ned variables in will never be matched to concrete values in any consistent extension of G and hence should be ruled out as an answer. On the other hand, if G [ GP is consistent, then such an extension exists and, by condition (C2), the unde ned variables can be mapped in this extension. De nition 2. Let R = (R; G; P; C; J K) be an entailment regime. A mapping is R-admissible for a graph G 2 C and legal graph pattern P if G [ GP is a graph belonging to C. The set of all R-admissible mappings for a consistent graph G and a legal graph pattern P is denoted as Adm(G; P ).

Example 4. Clearly, O1 [GP11 is inconsistent since ferries only depart from coastal cities, but Oxford is an inland city. In contrast, O1 [ GP21 is consistent. Thus, we have 1 2= Adm(O1; P ), but 2 2 Adm(O1; P ).

We are now ready to formalise our semantics.

De nition 3. Given an entailment regime R = (R; G; P; C; J K), the strict query answering function J Ks is de ned for legal graph patterns P and G 2 C as follows: 1. if P is a BGP then JP KsG = JP KG; 2. if P is P1 AND P2 then JP KsG = (JP1KsG on JP2KsG) \ Adm(G; P ); 3. if P is P1 OPT P2 then JP KsG = (JP1KsG on J s ) \ Adm(G; P ); and 4. if P is P 0 FILTER R then JP KsG = f j 2 JPP2K0KGsG and j= Rg, where \ denotes the standard set-theoretic intersection. If G 62 C then JP KsG = Err for any graph pattern P . Finally, legal patterns P1 and P2 are equivalent (under strict semantics), written P1 s P2, if JP1KsG = JP2KsG for any legal G. Example 5. The strict semantics behaves as expected for our examples: JP1KsO1 = s f 1g holds for O1 and P1 from Example 1, while JP2KO2 = ; holds for Example 2.

The strict and normative semantics coincide in two limit cases. First, if the entailment regime does not allow for inconsistent graphs (i.e., if C = G) as is the case for the RDF regime [ 10 ], then JP KsG = JP KnG for every legal pattern P and graph G. Second, if the relevant pattern P is OPT-free then the freezing for every candidate answer mapping contains no fresh IRIs and is R-entailed by G; thus, we again have JP KsG = JP KnG for every legal graph G.

Thus, the di erence between the normative semantics J Kn and strict semantics J Ks manifests only for regimes that admit inconsistency, and is circumscribed to the presence of OPT in graph patterns, where non-admissible mappings are excluded in the case of the strict semantics. Note, however, that even if a mapping 1 (respectively 2) is admissible for a subpattern P1 (respectively P2) containing OPT, it is possible for 1 [ 2 not to be admissible for the joined pattern P = P1 AND P2. Thus, the admissibility restriction is also explicitly re ected in the semantics of AND given in De nition 3. This is illustrated in the example given next.

Example 6. Consider ontology O3, consisting of the axioms SubClassOf(

IntersectionOf(SomeValuesFrom(husband Thing) SomeValuesFrom(wife Thing)) Nothing); ClassAssertion(Person Mary ): The rst axiom establishes that a person cannot have both a husband and a wife. Consider also the following well-designed graph pattern P3: (ClassAssertion(Person ?X) OPT (PropertyAssertion(husband ?X ?Y ))) AND (ClassAssertion(Person ?X) OPT (PropertyAssertion(wife ?X ?Z))): Clearly, = f?X 7! Mary g belongs to the strict answer to each of the OPT subpatterns of P3 since each of them independently can match to a consistent extension of O3. However, is not admissible for P3 since Mary has both a husband and a wife in GP3 , and hence O3 [ GP3 is inconsistent. Thus, JP3KO3 = ;. s 4.2

Comparing the Normative and Strict Semantics

Our previous examples support the expected behaviour of our semantics, namely that its e ect is circumscribed to ltering out problematic answers returned under the normative semantics. We next formally show that our semantics behaves as expected in general, provided that we restrict ourselves to well-designed patterns and negation-free FILTER expressions (which are rather mild restrictions).

It is known that patterns which are not well-designed easily lead to unexpected answers, even under the normative semantics (we refer to [ 2 ] for a detailed discussion). Therefore, it comes at no surprise that the intuitive behaviour of our semantics is only guaranteed under this assumption.

Theorem 1. Let R = (R; G; P; C; J K) be an entailment regime. The inclusion JP KsG v JP KnG holds for any graph G from C and any legal well-designed graph pattern P which does not use negation in FILTER expressions.

Note that Theorem 1 is formulated in terms of subsumption, instead of set-theoretic containment. The rationale behind this formulation is clari ed next. Example 7. Consider the ontology O10, which is obtained from O1 in Example 1 by removing all axioms involving Holyhead , and adding the axiom

PropertyAssertion(bus Canterbury London):

Consider also the following graph pattern P10:

PropertyAssertion(bus ?U ?X) OPT

(PropertyAssertion(train ?X ?Y ) OPT PropertyAssertion(ferry ?Y ?Z)): The mapping = f?U 7! Canterbury; ?X 7! London; ?Y 7! Oxford g is returned by the normative semantics. As already discussed, Oxford is an inland city and hence cannot have ferry connections; thus, is not returned under strict semantics. However, it may be possible to reach a ferry connection from London (although none is given), and hence the answer 0 = f?U 7! Canterbury; ?X 7! Londong is returned instead of under strict semantics. Clearly, 0 is not a normative answer and JP10KsO10 6 JP10KnO10 ; however, 0 v and JP10KsO10 v JP10KnO10 . 5

Computational Properties and Static Optimisation

In this section we rst study the computational properties of our semantics. We show that the complexity of graph pattern evaluation under strict and normative semantics coincide, provided that consistency checking is feasible in PSPACE for the regime at hand. Then we focus on static query analysis, and in particular on pattern equivalence. We show that the key equivalence-preserving transformation rules that have been proposed for static optimisation of SPARQL queries continue to hold if we consider equivalence under strict semantics. 5.1

Complexity of Strict Graph Pattern Evaluation

Recall that the graph pattern evaluation is the key problem in SPARQL. In the context of entailment regimes, it is de ned as follows, where x is either n or s.

Graph Pattern Evaluation Input : Regime R, legal graph G, legal graph pattern P , and mapping .

Question: Is 2 JP KxG under the regime R? Here, when we say that regime R is a part of the input, we mean that it includes two oracle functions checking consistency of legal graphs and evaluating legal BGPs over legal graphs, respectively. In what follows, we refer to the problem as Normative if x = n, and as Strict if x = s.

It is known that the normative graph pattern evaluation problem is in PSPACE for the RDF regime [ 2 ]. We next argue that membership in PSPACE holds in general for any regime satisfying the basic properties discussed in Section 2 and for both normative and strict versions of the problem, provided that the complexity of both oracles of the regime is in PSPACE.

Theorem 2. Normative and Strict Graph Pattern Evaluation problems are in PSPACE, provided the oracles associated to input regimes are in PSPACE.

Consequently, the use of our strict semantics does not increase the computational complexity for reasonable regimes. In particular, it follows directly from Theorem 2 that the evaluation problem is in PSPACE under both semantics for the tractable entailment regimes associated to the OWL 2 pro les [ 17 ].

It is also known that graph pattern evaluation under normative semantics is PSPACE-hard for the RDF regime [ 2 ]. To formulate a general hardness result that holds for any regime we would need to require additional properties for a regime to qualify as \reasonable". In order not to unnecessarily complicate the presentation, we simply point out that PSPACE-hardness holds for all the regimes in the speci cation under both normative and strict semantics [ 10 ]. 5.2

Static Analysis and Optimisation

Static analysis and optimisation of SPARQL queries has received signi cant attention in recent years [4, 6, 18{20]. A key ingredient for optimisation is the availability of a comprehensive catalog of equivalence-preserving transformation rules for SPARQL patterns. A rich set of such equivalences for normative semantics and RDF regime is established in [ 2 ] and [ 4 ]. Some of these equivalences, such as idempotence, commutativity, and associativity of the AND operator, hold without any restrictions (for our core fragment of SPARQL). However, those that involve OPT are more intricate and hold only for well-designed patterns. The claim of this section is that these equivalences continue to hold for any entailment regime, under both normative and strict semantics.

Theorem 3. The following equivalences hold for any entailment regime, provided

the graph patterns on both sides are legal and well-designed, for x 2 fn; sg: (P1 OPT P2) FILTER R

P1 AND (P2 OPT P3) (P1 OPT P2) OPT P3 x (P1 FILTER R) OPT P2; x (P1 AND P2) OPT P3; x (P1 OPT P3) OPT P2: 6

Conclusion

In this paper, we have proposed a novel semantics for optional matching in SPARQL under entailment regimes where unbound variables in answer mappings are naturally interpreted as \null" values. Our strict semantics has been designed to deal in a faithful way with the \lack of regular, complete structures in RDF graphs" and hence with the fundamental incompleteness of information on the Semantic Web [ 1 ]. We believe that both strict and normative semantics are valid, but one may be more appropriate than the other in certain applications. Both semantics are compatible at a fundamental level and it would be possible to exploit them in the same application by letting users commit to one or the other explicitly when posing queries. Integrating them in a clean way from a syntactic point of view is more tricky, and it is something we leave for future investigation.

References

1. Prud'hommeaux , E., Seaborne , A. : SPARQL query language for RDF . W3C Recommendation ( 2008 ) Available at http://www.w3.org/TR/rdf-sparql-query/.

2. Perez , J. , Arenas , M. , Gutierrez , C. : Semantics and complexity of SPARQL . ACM Trans. Database Syst . 34 ( 3 ) ( 2009 )

3. Angles , R. , Gutierrez , C. : The expressive power of SPARQL . In: ISWC. ( 2008 ) 114 { 129

4. Schmidt , M. , Meier , M. , Lausen , G.: Foundations of SPARQL query optimization . In: ICDT . ( 2010 ) 4 { 33

5. Arenas , M. , Perez , J.: Querying semantic web data with SPARQL . In: PODS. ( 2011 ) 305 { 316

6. Letelier , A. , Perez , J. , Pichler , R. , Skritek , S. : Static analysis and optimization of semantic web queries . ACM Trans. Database Syst . 38 ( 4 ) ( 2013 ) 25

7. Polleres , A. : From SPARQL to rules (and back) . In: WWW . ( 2007 ) 787 { 796

8. Motik , B. , Patel-Schneider , P.F. , Parsia , B. : OWL 2 Web Ontology Language Structural Speci cation and Functional-style Syntax . W3C Recommendation ( 2012 ) Available at http://www.w3.org/TR/owl2-syntax/.

9. W3C SPARQL Working Group: SPARQL 1.1 Query language . W3C Recommendation ( 2013 ) Available at http://www.w3.org/TR/sparql11-query/.

10. Glimm , B. , Ogbuji , C. : SPARQL 1.1 Entailment Regimes . W3C Recommendation ( 2013 ) Available at http://www.w3.org/TR/sparql11-entailment/.

11. Glimm , B. , Krotzsch, M.: SPARQL beyond subgraph matching . In: ISWC . ( 2010 ) 241 { 256

12. Kollia , I. , Glimm , B. : Optimizing SPARQL query answering over OWL ontologies . J. Artif. Intell. Res . 48 ( 2013 ) 253 { 303

13. Kontchakov , R. , Rezk , M. , Rodriguez-Muro , M. , Xiao , G. , Zakharyaschev , M. : Answering SPARQL queries over databases under OWL 2 QL entailment regime . In: ISWC . ( 2014 ) 552 { 567

14. Arenas , M. , Gottlob , G. , Pieris , A. : Expressive languages for querying the semantic web . In: PODS . ( 2014 ) 14 { 26

15. Kostylev , E.V. , Cuenca Grau , B. : On the semantics of SPARQL queries with optional matching under entailment regimes . In: ISWC . ( 2014 )

16. Perez , J. , Arenas , M. , Gutierrez , C. : Semantics and complexity of SPARQL . In: ISWC. ( 2006 ) 30 { 43

17. Motik , B. , Cuenca Grau , B. , Horrocks , I. , Wu , Z. , Fokoue , A. , Lutz , C. : OWL 2 Web Ontology Language : Pro les ( 27 October 2009 ) Available at http://www. w3.org/TR/owl2-profiles/.

18. Chekol , M.W. , Euzenat , J. , Geneves , P. , Layada, N.: SPARQL query containment under RDFS entailment regime . In: IJCAR . ( 2012 ) 134 { 148

19. Chekol , M.W. , Euzenat , J. , Geneves , P. , Layada, N.: SPARQL query containment under SHI axioms . In: AAAI. ( 2012 )

20. Chekol , M.W. , Euzenat , J. , Geneves , P. , Layada, N.: Evaluating and benchmarking SPARQL query containment solvers . In: ISWC . ( 2013 ) 408 { 423