SPARQL entailment regimes are strongly in uenced by the big body of works on ontology-based query answering, notably in the area of Description Logics (DLs). However, the semantics of query answering under SPARQL entailment regimes is de ned in a more naive and much less expressive way than the certain answer semantics usually adopted in database and DL literature. In this paper we introduce an intuitive certain answer semantics also for SPARQL and show the feasibility of this approach. For OWL 2 QL entailment, we develop algorithms for the evaluation of an interesting fragment of SPARQL (the so-called welldesigned SPARQL). Exploiting these algorithms, we can show that the complexity of neither query answering nor the most fundamental query analysis tasks (such as query containment and equivalence testing) is negatively a ected by the presence of OWL 2 QL entailment under the proposed semantics.
In the recently released recommendation [
The goal of this work is to introduce an intuitive certain answer semantics also for SPARQL under OWL 2 QL entailment with similarly favorable results as for CQ answering under DL-LiteR (which provides the theoretical underpinning of the OWL 2 QL entailment regime).
The reason why for this purpose we cannot simply take over all the results from CQ answering under DL-Lite is that SPARQL provides some crucial extensions over CQs. One of them is the OPTIONAL operator (henceforth referred to as OPT operator, for short). It allows the user to retrieve partial solutions in cases where no match for the complete query can be found, instead of failing to provide any solution. Observe that these queries are no longer monotone. Thus, the usual certain answer semantics (i.e., something is a certain answer if it is present in every model) turns out to be unsatisfactory: Example 2. Consider the SPARQL query: SELECT ?x; ?z WHERE (?x; teaches; ?y) OPT (?y; knows; ?z) over the graph G = f(b; teaches; c)g and empty ontology O. The query yields a unique solution = f?x ! bg. Clearly, also the extended graph G0 = G [ f(c; knows; d)g is a model of (G; O). But in G0, is no longer a solution since can be extended to solution 0 = f?x ! b; ?z ! dg. Hence, there exists no mapping which is a solution in every possible model of (G; O).
In this paper, we discuss further problems with a literal adoption of a certain
answer semantics in the presence of the OPT operator, and propose a suitable
modi ed de nition for the class of well-designed SPARQL queries [11]. This
modi ed semantics also requires an adaptation and extension of the known query
answering algorithms for DL-Lite. We present two such modi ed algorithms for
query evaluation. Finally, we shall show that the additional expressive power
due to the certain answers comes without an increase of the complexity.
Related Work. For our ndings the following work is most relevant to us:
the semantics of SPARQL was investigated in [
OWL 2 QL is based on DL-LiteR, a lightweight description logic. Its fundamental building blocks are constants c, atomic concepts A and atomic roles R, which are countably in nite and mutually disjoint subsets of a set U of URIs. From these we can build basic roles R and R , and basic concepts B and 9Q, where Q is a basic role. Using the above, DL-LiteR allows one to express the following kind of statements: Membership assertions (c; a; B) or (c; Q; c0), concept inclusions (B1; rdfs:sc; B2), role inclusions (Q1; rdfs:sp; Q2) as well as concept and role disjointness (where c; c0 are constants and Bi, Qi are basic concepts resp. basic roles). In the following, an ontology O is any set of such expressions, excluding membership assertions, which we assume to be part of the RDF graph. A knowledge base (KB) G = (G; O) consists of an RDF graph G and an ontology O.
The basic building block of SPARQL queries are triple patterns (s; p; o) 2 (U [ V)3, where V is a set of variables. In this work we only consider triple patterns of the form (?x; a; B) or (?x; Q; ?y) where B (Q) is a basic concept (role). More complex graph patterns are built from triple patterns via operators like e.g. AND, OPT, or UNION. Here, we consider a SPARQL query to be a graph pattern, possibly extended by top-level projection. Given a graph pattern P , a set X V of variables occurring in P and an RDF graph G, the answer J(P; X )KG to P , projected to X , over G is a set of partial mappings from X to U. We say a mapping 1 is subsumed by another mapping 2, denoted by 1 v 2, if dom( 1) dom( 2) and 1(?x) = 2(?x) for all ?x 2 dom( 1), where dom( i) denotes the set of variables the mapping i is de ned on.
By imposing certain restrictions on the occurrence of variables, the fragment
of well-designed SPARQL (wdSPARQL) was introduced in [11]. It possesses
several desirable properties, like coNP-completeness of query evaluation. Of
importance for our work is that these queries are weakly-monotone [
Before providing our de nition of certain answers, we need to introduce two additional notions. Let P be a well-designed graph pattern. Following [11], we say that P 0 is a reduction of P (denoted as P 0 E P ) if P 0 can be constructed from P by replacing in P sub-patterns of the form (P1 OPT P2) by P1. Second, for a mapping and some property A, we shall say that is v-maximal w.r.t. A if satis es A, and there is no 0 such that , and 0 satis es A. v 0, 0 6v De nition 1. Let G = (G; O) be a KB and Q = (P; X ) a well-designed query. A mapping is a certain answer to Q over G if it is a v-maximal mapping s.t. (1) v JQKG0 for every model G0 of G, and (2) vars(P 0) \ X = dom( ) for some P 0 E P . We denote by cert(P; X ; G) the set of all certain answers to Q over G. The reason for restricting the set of certain answers to v-maximal mappings is that queries with projection and/or UNION may have \subsumed" solutions, i.e. solutions s.t. also some proper extension is a solution. But then { with set semantics { we cannot recognize the reason why some subsumed solution is possibly not a solution in some possible world, as illustrated in Example 3. Since in our rst step towards reconciling SPARQL and certain answers we decide to stick to set semantics, we allow only \maximal" solutions as certain answers. Example 3. Consider the following query SELECT ?x; ?z WHERE (?x; teaches; ?y) OPT (?y; knows; ?z) over the graph G = f(a; teaches; b); (b; knows; c), (a; teaches; d)g and empty ontology O. As possible models of (G; O) we have all graphs containing G. Hence, = f?x ! a; ?z ! cg and 0 = f?x ! ag (?y is bound to d) are both answers to G and can be extended to solutions in every possible model.
Next consider G0 = f(a; teaches; b); (b; knows; c)g. If we take as certain answers all mappings that can be extended to some solution in every possible model, then 0 from above is still a certain answer.
Property (2) in the de nition of certain answers ensures that the domain of such an answer adheres to the structure of nested OPTs in the query. However, we can show that this property need not be considered during the computation of the certain answers, but can be enforced in a simple post-processing step. We call such answers that satisfy De nition 1 except property (2) certain pre-answers, and use certp(P; X ; G) to denote the set of all certain pre-answers. The same is also true for projection, which can also be performed in a simple post-processing step. Thus, it su ces to compute certp(P; G), which can be done via universal solutions (referred to as canonical model in the area of DLs) as follows. Theorem 1. Let G = (G; O) be a KB and P a well-designed graph pattern. Then, certp(P; G) = MAX(JP Kuniv(G)#), where MAX(M ) is the set of v-maximal mappings in M , M#:= f #j 2 M g ( # is the restriction of to those variables mapped to the active domain of G), and univ(G) is a universal solution of G.
However, computing the certain answers via a universal solution is not always
practical, e.g. the universal solution can be in nite. As a result, query rewriting
algorithms have been developed: These algorithms take the input query and
the ontology, and rewrite them into a single query that can be evaluated over
the input database without considering the ontology. By introducing several
adaptations and extensions of the rewriting-based CQ evaluation for DL-Lite
from [
The rst one proceeds in a modular way by rewriting basic building blocks of a SPARQL query (so-called BGPs) individually. It thus follows the general philosophy of SPARQL entailment regimes. One possible disadvantage of this modular approach is that it requires to maintain additional data structures to ensure consistency when combining the partial solutions for di erent BGPs. As a consequence, the complete algorithm has to be implemented from scratch because the standard tools cannot handle these additional data structures.
The goal of the second approach is thus to make use of the standard technology as much as possible. The idea is to transform the OWL 2 QL entailment under our new semantics into SPARQL query evaluation under RDFS entailment, for which strong tools are available. Unlike the rst { modular { approach, this rewriting proceeds in a holistic way, i.e. it always operates on the whole query.
Based on these rewriting algorithms, we analyze the complexity of query answering and of several static query analyzing tasks such as query containment and equivalence. We are able to show that the additional power of our new semantics comes without additional costs in terms of complexity. Acknowledgements This work was supported by the Vienna Science and Technology Fund (WWTF), project ICT12-15 and by the Austrian Science Fund (FWF): P25207-N23. 8. E. V. Kostylev and B. Cuenca Grau. On the semantics of SPARQL queries with optional matching under entailment regimes. In Proc. of ISWC 2014, 2014. 9. L. Libkin. Incomplete data: what went wrong, and how to x it. In Proc. of PODS 2014, pages 1{13. ACM, 2014. 10. M. Ortiz, D. Calvanese, and T. Eiter. Data complexity of query answering in expressive description logics via tableaux. Journal of Automated Reasoning, 41(1):61{ 98, 2008. 11. J. Perez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL.
ACM Trans. Database Syst., 34(3), 2009. 12. R. Rosati. On conjunctive query answering in EL. In Proc. of DL 2007, 2007.