Substantial research e orts have been invested into understanding the computational properties and expressive power of ontology-mediated queries (OMQs). Two important topics are the data complexity of OMQ evaluation [10, 12, 17, 5, 1], where only the data is considered to be the input while the OMQ is xed, and the rewritability of OMQs into more standard database query languages such as SQL (which in this context is often equated with rst-order logic) and Datalog [7, 3, 1, 11, 9]. Both subjects are thoroughly intertwined. In particular, rewritability into rst-order logic (FO) is closely related to AC0 data complexity while rewritability into Datalog is closely related to PTime data complexity. Traditionally, data complexity and rewritability have mostly been studied on the level of OMQ languages (L; Q) de ned by an ontology language L such as E L and a query language Q such as conjunctive queries (CQs). A more ne-grained analysis has been initiated in [16, 1], the aim being to understand the exact complexity and rewritability status of every OMQ from relevant OMQ languages (L; Q), see also [18, 15]. For expressive DLs, this turns out to be closely related to the complexity classi cation of constraint satisfaction problems (CSPs) with a xed template [8]. Very important progress has recently been made in this area with the proof that CSPs enjoy a dichotomy between PTime and NP [4, 19]. Via the results in [1], this implies that OMQ evaluation in languages such as (ALCI; UCQ) enjoys a dichotomy between PTime and coNP. However, the complexity of CSPs and OMQs is still far from being fully understood. For example, neither in CSP nor in expressive OMQ languages it is known whether there is a dichotomy between NL and PTime, and whether containment in NL coincides with rewritability into linear Datalog, a well-known fragment of Datalog that allows only linear recursion. It has been conjectured that both of this is the case. We report on [14], which carries out a ne-grained analysis of the data complexity and rewritability of OMQs from (E L; CQ), achieving a complete classication. This extends the results of [13] where the same was achieved for the OMQ language (E L; AQ) that only admits atomic queries, that is, conjunctive queries of the very simple form A(x). For every Q 2 (E L; CQ), let eval(Q) be
the problem to decide, given an ABox A and a tuple of individuals a, whether a is a certain answer to Q on A. Our main result is the following trichotomy. Theorem 1. For every OMQ Q 2 (E L; CQ), one of the following is true: 1. eval(Q) is in AC0 and Q is rewritable into FO (actually into a UCQ with equality atoms); 2. eval(Q) is NL-complete and Q is rewritable into linear Datalog; 3. eval(Q) is PTime-complete and Q is rewritable into monadic Datalog. Consequently, eval(Q) is in NL if and only if Q is rewritable into linear Datalog unless NL = PTime.
An important aspect of the proof of Theorem 1 are semantic characterizations of the three cases, which are also interesting in their own right. The characterizations are easiest to state for AQs. For Q 2 (E L; AQ), let MQ denote the set of all tree shaped ABoxes whose root is a certain answer to Q and that are minimal with that property regarding set inclusion. We say that Q has bounded depth if there is a constant bound on the depth of the trees in MQ and Q has bounded pathwidth if there is a constant bound on the pathwidth of the trees in MQ; recall that pathwidth measures the similarity of a structure to a path with lower number meaning more similar. For CQs, the de nitions are similar, but for de ning MQ we consider ABoxes of a certain pseudo-tree shape instead of tree shaped ones.
While it is known that bounded depth of an OMQ from (E L; CQ) implies
FO-rewritability [2], we prove that
(
The proofs are technically subtle, especially the hardness proofs (
There are several natural directions into which our results can be generalized. One is to consider the OMQ language (E L; UCQ). We conjecture that this generalization is not di cult. In fact, we only refrained from covering it since it makes all proofs more technical and distracts from the main ideas. An important direction for future work is to extend our analysis to E LI, that is, to add inverse roles. Even the case of (E LI; AQ) appears to be challenging. In fact, we observe that a complexity classi cation of (E LI; AQ) is equivalent to a complexity classi cation of all CSPs that have tree obstructions, which is an open Classifying the Complexity of Ontology-Mediated Queries in EL problem. It is easy to see that (E LI; AQ) contains OMQs that are L-complete and we conjecture that AC0, L, NL, and PTime are the only complexities that occur. We also conjecture that L-completeness coincides with rewritability into symmetric Datalog [6].
Acknowledgments. This research was supported by ERC consolidator grant 647289 CODA.