Ontology-mediated queries (OMQs) based on description logic (DL) ontologies and their complexity have been a subject of intense study [5, 7, 8]. In the full paper [1] reported on in this abstract, we explore the frontiers of two important notions of tractability for OMQs, PTime combined complexity and xedparameter tractability (FPT) where the parameter is the size of the OMQ. Given that ontologies can get large in practice, these notions of tractability are arguably more realistic than PTime data complexity as frequently considered in the literature [9, 11, 16, 17]. As usual, we use (L; Q) to denote the OMQ language where ontologies are formulated in the DL L and queries are from the query language Q. From now on, we generally mean combined complexity when speaking of complexity. There are only few OMQ languages that have PTime complexity or are FPT (with the parameter being the size of the OMQ) without imposing serious restrictions on the shape of the query or the ontology. An important example for the former is dr; AQ) where dr stands for domain and range restrictions and AQ refers (E LH? to the class of atomic queries of the form A(x), A a concept name; this result is implicit in [18]. An important example for an OMQ language that is FPT is (E LHI?; AQ); we are not aware of this being stated explicitly anywhere, but it is not too hard to prove using standard means. Note that the (unrestricted) use of the popular conjunctive queries (CQs) and unions thereof (UCQs) as the query language Q rules out both of the considered complexities independently of the choice of L since (U)CQ-evaluation (without an ontology) is NP-complete and W[1]-hard, thus most likely not xed-parameter tractable [14]. A seminal result by Grohe precisely characterizes the (recursively enumerable) classes of CQs over schemas of bounded arity that can be evaluated in PTime: this is the case if and only if for some k, every CQ in the class is equivalent to a CQ of tree width k, unless the assumption from parameterized complexity theory that FPT 6= W[1] fails [15]. Grohe's result also establishes that PTime complexity and FPT coincide for evaluating CQs (for schemas of bounded arity). A generalization to UCQs has been observed by Chen [10]. It has further been observed in [6] that whenever Q is a class of CQs that can be evaluated in PTime, then the same is true for OMQs from (E LH; Q). In particular, Q might be the class of CQs of tree width bounded by some k. The main aim of the work that we report about is to precisely analyze the frontiers of PTime complexity and FPT for OMQs in which the ontology language is from the E L and E LI families of DLs and where Q are (U)CQs. An Supported by ERC grant CODA, EPSRC grant EQUID, the Millennium Institute for Foundational Research on Data, and Fondecyt grant 1170109.
OMQ has bounded tree width if the actual query in it has. Our main contributions
are the following, assuming that FPT 6= W[
dr; UCQ) that admit PTime evaluation are exactly 1. the subclasses of (E LH?
those in which each OMQ is equivalent to an OMQ of bounded tree width; 2. the subclasses of (E LHI?; UCQ) for which evaluation is in FPT are exactly those in which each OMQ is equivalent to an OMQ of bounded tree width. In Point 1 (but not in Point 2), we assume that the ABox signature is full. Regarding Point 2, we also show that the runtime of the FPT algorithm can be made single exponential in the parameter. Given that E LHd?r is a fragment of E LHId?r;, UPCoiQnt)sw1heanndth2e iAmBployx tshigantaPtuTriemies fcuolml. pFleoxrittyhean`udpFpePrTbocuonindc'idoef in (E LH? Point 2, we use existential pebble games adapted in a careful way to OMQs. For the rather non-trivial `lower bound', we build on Grohe's result. Dealing with non-full ABox signatures is a serious challenge as standard techniques from relational databases such as using the core of a CQ must be replaced by more subtle ones. In Points 1 and 2, equivalence to an OMQ Q of bounded tree width includes the case that Q uses a di erent ontology than the original OMQ. We also show, however, that in most cases there is no bene t in changing the ontology.
We point out that our tractability results are stronger than those in [
We further study the complexity of the meta problem of deciding whether
a given OMQ is equivalent to an OMQ of bounded tree width. Our results
range from 2p between (DL-LiteR; CQ) and (DL-LitehRorn; UCQ) via ExpTime
dr; UCQ) to 2ExpTime between (E LI; CQ) and
between (E L; CQ) and (E LH?
(E LHI?; UCQ). As an important special case, we consider the full ABox
signature. There, the complexity drops considerably, to NP, NP, and ExpTime,
respectively. The case of the full ABox signature is also interesting because it
admits constructions that are close to the case of relational databases, such as (a
suitably adapted version of) retracts. Under the full ABox signature, the
problems studied here are related to the the evaluation of (U)CQs of bounded tree
width over relational databases with integrity constraints [
We also take a rst glimpse at OMQ languages based on DL-LiteF . This turns
out to be closely related to the evaluation of UCQs over relational databases in
the presence of key dependencies, as studied by Figueira [