Introduction
Conjunctive Queries (CQs) constitute the core of most query languages and
have been studied intensively in several areas. For querying incomplete data,
CQs however su er one major drawback: they require the complete query to be
matched into the data to return answers. One extension of CQs that tries to
overcome this problem are well-designed pattern trees (wdPTs) [
Because of this feature, however, wdPTs are nonmonotone. This is problematic
for query answering in the presence of implicit knowledge { expressed e.g. by
an ontology speci ed in some Description Logic (DL) { since the usual certain
answer semantics turns out to be unsatisfactory in this setting. We observe that
the recently released recommendation of the SPARQL entailment regimes [
The goal of this work is to introduce an intuitive certain answer semantics for the class of well-designed pattern trees under DL-LiteR (which provides the theoretical underpinning of the OWL 2 QL entailment regime). After introducing wdPTs, we rst discuss some of the problems with an adoption of a certain answer semantics for them and propose a suitable modi ed de nition. We then brie y present results on the complexity of typical reasoning tasks.
Related Work to our ndings includes the work our approaches are based
upon [3{6]. There is a huge body of results on CQ answering under di erent DLs
(cf. [
DL-LiteR and Well-designed Pattern Trees
We assume the reader to be familiar with DL-LiteR [
A well-designed pattern tree P is a tuple (T; ; x) such that: 1. T is a rooted tree and maps each node t in T to a conjunctive query (CQ).
A CQ here is a set of atoms, where atoms are built as usual, i.e. from concept and role names together with individuals and variables. 2. For every variable y occurring in T , the set of nodes containing y is connected. 3. x is a tuple of variables from T , called the free variables of P. Intuitively, the parent-child relationships in the tree express optional matching. I.e., the result of the \parent-CQ" shall be extended by the \child-CQ" if possible | otherwise the child shall be ignored, and only the result of the parent is returned. Finally x are the \output" variables.
A mapping is any partial function whose domain dom( ) contains only variables. We say a mapping 1 is subsumbed 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). Also, 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 v 0, 0 6v , and 0 satis es A. For any mapping and a tuple of variables x, we denote by x the restriction of to the variables in x.
The notion of a mapping that is a match for a CQ q in an interpretation I is
de ned in the standard way. Assume a wdPT P = (T; ; x) and an interpretation
I. For an initial segment T 0 of T , i.e. a connected subgraph containing the root
of T , we de ne qT 0 to be the CQ St2T 0 (t). Then a match for P in I is any
mapping such that is a match for qT 0 in I for some initial segment T 0 of
T . Let M be the set of all v-maximal matches from P to I. Then the result of
evaluating P over I, projected to x, is the set JPKI = f x j 2 M g. Note that
the order of child nodes in such tress does not a ect the query answer (see [
In the following example, we illustrate wdPTs as well as the reason why the usual certain answer semantics (i.e., a tuple is a certain answer if it is present in every model) turns out to be unsatisfactory in our setting: Example 1. Let P be the wdPT (T; ; x) where T consists of the root r with the single child t, (r) = fteaches(x; y)g, (t) = fknows(y; z)g, and x = fx; zg. Consider the KB K consisting of an ABox A = fProf(b)g, and a TBox T = f(Prof v 9teaches)g. Let I be as follows: ProfI = f(b)g. Clearly, I j= K. The query yields in I as only answer the mapping = fx ! bg. Clearly, also the interpretation I0, where ProfI0 = f(b)g, teachesI0 = f(b; c)g and knowsI0 = f(c; d)g is a model of K. But in I0, is no longer an answer since can be extended to answer 0 = fx ! b; z ! dg. Hence, there is no mapping which is an answer in every possible model of K.
De nition 1. Let K = (A; T ) be a KB and P = (T; ; x) a wdPT. A mapping is a certain answer to P over K if it is a v-maximal mapping s.t. (1) v JPKI for every model I of K, and (2) vars(qT 0 ) \ x = dom( ) for some initial segment T 0 of T . We denote by cert(P; K) the set of certain answers to P over K. The reason for restricting the set of certain answers to v-maximal mappings is that wdPTs in general may have \subsumed" answers, i.e. mappings s.t. also some proper extension is an answer. But then { with set semantics { we cannot recognize the reason why some subsumed answer is possibly not an answer in some possible world. Therefore, in our rst step towards extending CQs by optional matching, we allow only \maximal" answers as certain answers.
Property (2) ensures that the domain of such an answer adheres to the tree
structure of the wdPT. However, we can show that this can be enforced in
a simple post-processing step. Likewise, also projection can be deferred to a
post-processing step. The task is thus to compute a set certp(P; K) of certain
pre-answers (i.e., mappings that satisfy De nition 1 except property (2), ignoring
projection), which can be done via the canonical model. For a given KB K, we
assume a canonical model of K, denoted as can(K), to be de ned as in [
To cope with the potential in nite canonical model, query rewriting algorithms
have been developed in the literature. By introducing several adaptations and
extensions of the rewriting-based CQ evaluation for DL-Lite from [
For future work, we want to investigate further more expressive DLs under our certain answer semantics. The implementation of the rewriting algorithms and the development of suitable benchmarks, is a challenging task as well. Additionally, we will extend our work to allow TBox queries and other fragments of SPARQL. 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 and W1255-N23. 1 Note that, in the full version we consider a fragment of well-designed SPARQL under
OWL 2 QL entailment, which corresponds exactly to what we consider here.