Despite the intention of RDF, the data model for the Semantic Web, to support reasoning about RDF data (as witnessed e.g. by three di erent semantics for RDF { simple/RDF/RDFS entailment { or accompanying standards like OWL), SPARQL, the standardized query language for RDF, lacks some support of including such reasoning into query answering, as was noted e.g. in [6, 1]. One major cause of this is that SPARQL only makes partially use of certain answers, which are the semantics commonly applied in reasoning scenarios. While not fully supporting certain answers might be a reasonable decision when looking at the costs of evaluating and (for a user) understanding a query, it negatively a ects the power of SPARQL. As a result, in recent years suggestions have been made how to cover di erent aspects of reasoning about RDF data (e.g. blank nodes under RDF simple entailment [6]; OWL reasoning [1]) in SPARQL by adopting a certain answer semantics. However, as observed in [1], just applying the usual de nition of certain answers to SPARQL can, in certain cases, be unnecessarily restrictive. To better illustrate these situations, let us rst recall the de nition of certain answers. Given an RDF graph G (possibly extended by some additional information), most reasoning formalisms de ne the semantics of G in terms of an (in nite) set models(G) of RDF graphs implied by G. Query answering in such a setting is then commonly de ned in terms of the certain answer semantic: for a query Q, the certain answers certain(Q; G) (w.r.t. some reasoning formalism) are certain(Q; G) = TG02models(G) Q(G0), where Q(G0) denotes the result of evaluating Q over the RDF graph G0. While this de nition can be immediately applied to SPARQL queries, problems arise e.g. when looking at the OPTIONAL operator, or more precisely at the weakly monotone classes of SPARQL queries, like the well-designed queries [10]. Example 1. Consider the SPARQL query Q SELECT ?auth; ?award WHERE f?auth writes ?bg OPTIONAL f?b receives ?awardg and an RDF graph G = f(a; writes; b)g. Assuming that models(G) contains all supersets of G (like e.g. under the RDF simple semantics), certain(Q; G) = ;.
Given that (a; writes; b) 2 G0 for every G0 2 models(G), this is an
unintuitive result. However, the mapping = f(?auth; a)g is no certain answer
because it is not part of Q(G0) for every G0 2 models(G). For example, take
G0 = G [ f(b; receives; p)g. Then Q(G0) = ff(?auth; a); (?award; p)gg.
What makes this situation unintuitive is that while 2= Q(G0), an extension
of is contained in Q(G0). In fact, weakly monotone queries are exactly those
queries Q where for all pairs of RDF graphs G G0 the result Q(G0) contains a
not necessarily proper extension of every mapping in Q(G) [
To account for this, based on the notion of subsumption (a mapping 0
subsumes a mapping if 0 extends ), an alternative certain answer semantics was
proposed in [
Example 2. Consider the query Q from Example 1 and let the RDF graph G1 be
the RDF graph G0 from Example 1. Assuming models(G1) to contain all
supersets of G1, one would expect certain(Q; G1) = ff(?auth; a); (?award; p)gg, while
there is no justi cation for f(?auth; a)g 2 certain(Q; G1). However, for G2 =
G1 [ f(a; writes; c)g, intuitively certain(Q; G2) = ff(?auth; a); (?award; p)g;
f(?auth; a)gg. This is because, unlike for G1, over each graph in models(G2) at
least two di erent mappings contribute a solution, namely f(?auth; a); (?b; b);
(?award; p)g and f(?auth; a); (?b; c)g. However, due to projection, these two
mappings may lead to the same solution: for G3 = G2 [f(c; receives; p)g we get
(under set semantics) Q(G1) = Q(G3). Under bag semantics, Q(G1) and Q(G3)
still contain the same mapping, but it occurs once in Q(G1) and twice in Q(G3).
As a result, these two cases cannot be distinguished under set semantics, which
prevents a de nition of certain answers that acknowledges the di erences
between these cases. In [
Given recent advances in SPARQL query answering and reasoning under bag
semantics (cf. [
A possible way of de ning a certain answer semantics that faithfully includes subsumed mappings is to introduce a \subsumption-aware" variant of bag-intersection.
Towards this goal, we x some notation. A mapping is a set of pairs (?xi; vi), each pair denoting (?xi) = vi. A bag M of mappings is a collection of mappings that may contain each mapping more than once. We write card M ( ) to denote the number of times a mapping occurs in bag M (if clear, M may be dropped; if we do not specify card M ( ), we assume 1 by default). In this submission, we will assume RDF graphs to be sets, while we assume query results to be bags of mappings, a setting sometimes referred to as set-bag semantics in the literature.
Having settled this, we rst have to extend the notion of subsumption to
bags. For sets L, R of mappings, subsumption L v R holds when for every
mapping 2 L there exists a mapping 0 2 R such that 0. Similar to
homomorphisms (cf. [
We thus use a stricter de nition for subsumption between bags, and say that a
bag L is subsumed by a bag R, written L vb R, if there exists a mapping h : L !
R such that v h( ) for all 2 L and card R( 0) P 2L : h( )= 0 card L( ) for
all 0 2 R (this corresponds to the additive homomorphisms in [
Next, we say that a bag M of mappings is vb maximal w.r.t. a property if M satis es and there is no M 0 satisfying such that M v M 0 but M 0 6v M .
It is an interesting observation at this point that sets M1 6= M2 of mappings may satisfy M1 v M2 and M2 v M1 (just consider the mappings in Example 2), while (for bags or sets) B1 vb B2 and B2 vb B1 implies B1 = B2.
The notion of vb-maximal bags now allows us to de ne L \v R, a version of bag-intersection that retrieves maximal information from both, L and R: for two bags L, R of mappings, let L \v R be a vb-maximal bag M such that M vb L and M vb R. Unfortunately, the result of this operator is not necessarily unique. Example 3. Let L = ff(x; 1); (y; 1); (u; 1)g; f(v; 1)gg and R = ff(x; 1); (y; 1); (v; 1)g; f(u; 1)gg be two bags of mappings. Then M1 = ff(x; 1); (y; 1)gg and M2 = ff(u; 1)g; f(v; 1)gg are both vb-maximal w.r.t. being subsumed by L and R. However, we will discuss next that in many cases \v, or a slight adaption of it, is nevertheless well-suited to de ne meaningful certain answers. 3
Certain Answers via \v Besides not returning a unique bag, another property of \v needs to be taken care of before it can be used to de ne certain answers, as illustrated next. Example 4. Consider a SPARQL query Q SELECT ?a; ?w; ?r WHERE f?a isa authorg OPTIONAL f?a writes ?w:?a reads ?rg and an RDF graph G = f(a; isa; author); (a; reads; b)g. Assume that also the knowledge \every author writes some book" (expressed e.g. in OWL) is given and that every RDF graph G0 2 models(G) satis es this condition. Then Tvfq(G0) j G0 2 models(G)g = ff(?a; a); (?r; b)gg.
However, this result does not respect the requirement expressed in the query that
a result should contain either a value for both, ?w and ?r, or neither of them. As
a result, instead of de ning certain answers just as Tvfq(G0) j G0 2 models(G)g,
following [
Finally, for a query Q, let the admissible solution domains adsoldom (Q) be the set of possible domains of mappings in Q(G) (for any G). Due to space restrictions we stick to this vague de nition; but, for example, for conjunctive queries Q, adsoldom(Q) contains as single element the set of all output variables of Q, for query Q from Example 2 we get adsoldom(Q) = ff?authg; f?auth; ?awardgg, and for Q from Example 4, adsoldom(Q) = ff?ag; f?a; ?w; ?rgg.
De nition 1. Let G be an RDF graph, Q a query, and models (G0) the set of graphs entailed by G. Then the certain answers of Q are de ned as certain(Q; G) = Tadsoldom(Q)fQ(G0) j G0 2 models(G)g:
v
While, for arbitrary inputs L; R; V, the result of L \Vv R is not necessarily unique, in most of the settings in which we compute certain answers, L, R, and V are not arbitrary inputs but adhere to some structure that we can exploit.
For example, when applied to conjunctive queries, \v V reduces to conventional (set- or bag) intersection, and as a result for these queries we get the \classical" de nition of certain answers as a special case of De nition 1.
Similarly, in the special case of models(G) containing a minimal element G (i.e. G G0 for all G0 2 models(G)), for weakly monotone SPARQL queries the certain answers are uniquely de ned. In fact, applied to the settings in Examples 1 and 2 it produces exactly the intuitive bags of certain answers.
More generally, also for the sets models(G) that exhibit a canonical model (i.e. that contain some G0 2 models(G) such that for every Gi 2 models(G) there exists some homomorphism hi : G0 ! Gi) we strongly conjecture that for weakly monotone queries, and especially for well-designed SPARQL queries, De nition 1 gives a unique bag of certain answers.
There are, of course, a lot of open question for future and ongoing work.
These include the relationship to certain answer semantics from the literature
(e.g., while \typical" certain answers for CQs are a special case of De nition 1,
this seems not to be the case for the de nition in [