The complexity of ontology-mediated querying in popular expressive description logics (DLs) such as ALC and ALCI is prohibitively high, namely coNPcomplete in data complexity [4] and ExpTime- resp. 2ExpTime-complete in combined complexity [3]. As a consequence, practical implementations resort to approximations of ontology mediated queries (OMQs) [6, 5, 7] that are, however, often of a rather pragmatic nature. The work reported about in this abstract is concerned with a systematic study of OMQ approximations that achieve the following desiderata [2]: (i) PTime data complexity, (ii) xed-parameter tractability (FPT) with the parameter being the size of the OMQ (if possible) and (iii) improved combined complexity (if possible), We mainly consider approximation from below, that is, approximations that are sound, but (potentially) incomplete. Recall that an OMQ is a triple Q = (O; ; q) where O is an ontology, q an actual query such as a conjunctive query (CQ), and a signature for the databases D that Q is evaluated on. Our starting point is the observation that we may attain (the only non-optional) desideratum (i) by relaxing the ontology O or the database D. Note that relaxing the query q is not promising towards this aim as ontology-mediated querying is coNP-hard already for atomic queries (AQs), that is, CQs of the form A(x). For ontology relaxing approximation, we choose a DL L for which ontologymediated querying is in PTime in data complexity. We then replace O with every L-ontology O0 such that O j= O0 (which guarantees soundness) and take the union of all answers. As choices for L, we consider Horn description logics such as E LI and frontier-one tuple-generating dependencies (TGDs) [1] with the treewidth of the body and head bounded by a constant. For database relaxing approximation, we choose a class D of databases for which ontology-mediated querying is in PTime in data complexity. We then replace D with every database D0 2 D such that there is a homomorphism from D0 to D (which guarantees soundness) and then take the union of all answers. As choices for D, we consider databases of bounded treewidth and databases that are proper trees. An OMQ language is a pair (L; Q) with L an ontology language and Q a query language. We study the approximation of OMQ languages (L; Q) with
L 2 fALC; ALCIg and Q 2 fUCQ; CQ; AQ; bELIQg where UCQ denotes unions of CQs and bELIQ denotes the class of unary CQs that correspond to E LIconcepts (ELIQs) and of Boolean CQs 9x q(x) with q(x) an ELIQ. The exact problem studied is approximate OMQ evaluation, meaning to decide, given an OMQ Q, a database D, and a tuple a of constants from D, whether a is an approximate answer to Q on D.
In this abstract, we only state explicitly two main results, the rst one concerning ontology relaxing approximation.
Theorem 1. Let L 2 fALC; ALCIg and `; k; k0 ontology relaxing evaluation is 1 with ` < k. Then `; k; 1; k01. ExpTime-complete in combined complexity and PTime-complete in data complexity in (L; Q), Q 2 fAQ; CQ; UCQg; 2. FPT in (L; Q), Q 2 fCQtpw; UCQtpw j p 1g.
Let us clarify notation. A CQ has treewidth at most (`; k) if it admits a tree decomposition in which the size of the bags is bounded by k and the overlap between the bags is bounded by `: Then, `; k; 1; k0-ontology relaxing evaluation means that we replace O with every set of frontier-one TGDs O0 such that O j= O0 and the TGDs in O0 are such that the treewidth of their bodies is at most (`; k) while the treewidth of their heads is at most (1; k0). With CQtpw, we mean CQs of treewidth bounded by the constant p and UCQtpw means disjunctions of CQs from CQtpw. Note that ontology relaxing approximation indeed achieves desideratum (i) and that in the case of ALCI, it additionally achieves desideratum (iii). Desideratum (ii) is only achieved for (U)CQs of bounded treewidth. In the full paper, we also study ontology relaxing approximation using the DL u in place of TGDs, where we additionally attain linear time data complexE LI? ity for (ALCI; bELIQ).
The second main theorem concerns database relaxing approximation. Theorem 2. Let 1
` < k. Then `; k-database relaxing evaluation is 1. 2ExpTime-complete in combined complexity and FPT (thus in PTime in data complexity) in (ALCI; Q), Q 2 fCQ; UCQ; CQtpw; UCQtpw j p 1g; 2. ExpTime-complete in combined complexity and FPT in (ALC; Q) and in (ALCI; Q), Q 2 fAQ; bELIQg.
Here, `; k-database relaxing evaluation means that we replace the input database D with every database D0 of treewidth at most (`; k) that admits a homomorphism to D. Thus also database relaxing approximations achieve desideratum (i). In contrast to ontology relaxing approximations, there are no cases where desideratum (iii) is achieved. However, desideratum (ii) is achieved for a much wider class of queries.
In the full paper, we also study database relaxing approximation using proper trees in place of databases of bounded treewidth for which Point 2 of Theorem 2 can be strengthened to linear time in data complexity (which implies FPT). We also make the surprising observation that tree-database relaxing evaluation How to Approximate Ontology-Mediated Queries is ExpSpace-hard in (ALC; CQ) and 2ExpTime-hard in (ALC; UCQ), thus harder than non-approximate evaluation which is ExpTime-complete.
We also study approximation from above in the form of ontology strengthening approximation and database strengthening approximation. These are de ned dually to ontology/database relaxing approximations and are complete, but (potentially) unsound. For L-ontology strengthening approximation, we replace O with every L-ontology O0 such that O0 j= O (which guarantees completeness) and take the intersection of all answers. For D-database strengthening approximation, we replace D with every database D0 2 D such that there is a homomorphism from D to D0 (which guarantees completeness) and then take the intersection of all answers.
It turns out that ontology strengthening approximation and database strengthening approximation are less well-behaved than their counterparts that approximate from below. We state the two main theorems that illustrate this. Recall that E LIU ? is the fragment of ALCI that extends E LI? with disjunction. Theorem 3. Let Q 2 fAQ; CQ; UCQg. E LI?-ontology strengthening evaluation in (E LIU ?; Q) is 2ExpTime-complete in combined complexity and FPT.
So E LI?-ontology strengthening evaluation satis es desiderata (i) and (ii),
but not (iii). In fact, we consider the lower bound for (E LIU ?; AQ) surprising as
non-approximate evaluation is only ExpTime-complete [
For the second theorem, we use D1 to denote the class of databases that are disjoint unions of trees, multi-edge and self-loops admitted.
Theorem 4. D1-database strengthening approximation is coNP-complete in data complexity in (ALCI; UCQ). The lower bound already holds when the ontology is empty. It also holds in (E L; CQ).
Thus, D1-database strengthening approximation does not satisfy our crucial desideratum (i). For (E L; CQ), the data complexity even increases from PTime to coNP-complete when transitioning from non-approximate evaluation to the approximate version.
Acknowledgement. Anneke Haga and Carsten Lutz were supported by DFG CRC 1320 Ease. Frank Wolter was supported by EPSRC grant EP/S032207/1.