In data access with ontologies [9, 17, 7], query rewriting is a central approach to e cient query anwering using existing database technology. Due to the tight connection between SQL and rst-order logic (FO), FO queries are one of the most important target languages for rewriting. In this abstract, we consider FO-rewriting of ontology-mediated queries in the case when the actual query is a conjunctive query and the ontology is formulated in a DL between EL and Horn-SHIF . In contrast to the case of DL-Lite [10], FO-rewritings are not guaranteed to exist when working with these more expressive DLs. A natural rst step to approach the actual construction of FO-rewritings (when they exist) is thus to nd an algorithm that decides the existence of a rewriting; in fact, any complete and terminating algorithm for constructing rewritings will implicitly also solve the decision problem and one can expect to learn important lessons already from the latter. It turns out that FO-rewritability is closely related to query containment problems as studied in [5, 8]. For this reason, we also provide results for query containment. For the case of atomic queries (AQs) and DLs between EL and Horn-SHI, it has been proved in [6] that FO-rewritability is ExpTime-complete (in the presence of an ABox signature). Our main result is that, when replacing AQs with CQs, this complexity does not change for DLs without inverse roles and jumps to 2ExpTime for DLs with inverse roles. The latter result is relativized by the observation that there is an algorithm that has double exponential runtime only in the size of the actual queries (which tend to be small), but single exponential runtime in the size of the ontology (which tends to be large). We also show NExpTime-completeness for the case where queries are connected and have at least one answer variable, and where the DL includes inverse roles. Our results also yield improved lower bounds for FO-rewritability and containment in monadic Datalog, compared to those in [12, 3, 2].
Related work. As has already been mentioned, the case of AQs was addressed
in [
Pragmatic approaches to OMQ rewriting beyond DL-Lite often consider
Datalog as a target language [13, 16, 20{22]. These approaches might produce
a non-recursive (thus FO) rewriting if it exists, but there are no guarantees.
FO-rewritability of OMQs based on expressive DLs is considered in [
Let an ontology-mediated query (OMQ) be a triple (T ; ; q) with T a DL TBox, an ABox signature (set of concept and role names), and q an actual query. We use (L; Q) to denote the OMQ language that consists of all OMQs where T is formulated in the description logic L and q in the query language Q. Our main complexity results concern FO-rewritability and containment for OMQ languages between (EL, AQ) and (Horn-SHIF , CQ).
Theorem 1. FO-rewritability and containment are 1. 2 ExpTime-complete for any OMQ language between (ELI, CQ) and (Horn
SHIF , CQ), and 2. ExpTime-complete for any OMQ language between (EL, AQ) and (ELHF?,
CQ).
Moreover, given an OMQ from (Horn-SHIF ; CQ) that is FO-rewritable, one can e ectively construct a UCQ-rewriting.
Thus, replacing AQs with CQs results in an increase of complexity in the presence
of inverse roles (indicated by I), but not otherwise. The e ect that inverse roles can
increase the complexity of querying-related problems was known from expressive
DLs of the ALC family [
The upper bounds in Theorem 2 rely on characterizations FO-rewritability
and containment that are extensions of those in [
Theorem 2. Let L be any of the languages in Theorem 1. Then FO-rewritability in (L; CQ) can be solved in polynomial time when there is access to oracles for containment in (L; Q) and for FO-rewritability in (L; conCQ).
This allows to avoid rather unpleasant technical complications; note that
complications due to disconnectedness have been observed also in monadic
Datalog boundedness such as the classical [
The jump in complexity from ExpTime to 2ExpTime might appear to be problematic, but this is relativized when analyzing the upper bound in Point 1 of Theorem 1 a bit more carefully: Theorem 3. Given OMQs Qi = (Ti; i; qi), i 2 f1; 2g, from (Horn-SHIF , CQ), it can be decided 1. in time 22p(jq1j+log(jT1j)) whether Q1 is FO-rewritable and 2. in time 22p(jq1j+jq2j+log(jT1j+jT2j)) whether Q1 Q2, for some polynomial p.
Note that the runtime is double exponential only in the size of the actual queries q1 and q2, while it is only single exponential in the size of the TBoxes T1 and T2. This is good news since the size of q1 and q2 is typically very small compared to the sizes of T1 and T2. For this reason, it can even be reasonable to assume that the sizes of q1 and q2 are constant, in the same way in which the size of the query is assumed to be constant in data complexity. Note that, under this assumption, Theorem 3 yields ExpTime upper bounds for FO-rewritability and containment in the OMQ languages listed in Point 1 of Theorem 1.
Another interesting way to relativize the high complexity stated in Point 1 of Theorem 1 is to observe that the lower bound proofs require the actual query to be Boolean or disconnected. In practical applications, though, typical queries are connected and have at least one answer variable. We call such CQs rooted and use rCQ to denote the class of all rooted CQs. Our last main result states that, when we restrict our attention to rooted CQs, then the complexity drops to coNExpTime.
Theorem 4. FO-rewritability and containment are coNExpTime-complete in any OMQ language between (ELI; rCQ) and (Horn-SHIF ; rCQ). As mentioned in the introduction, the lower bound proofs underlying Theorem 1 also yield improved lower bounds for FO-rewritability and containment in monadic Datalog.
Corollary 1. Containment and boundedness of monadic Datalog programs are 2 ExpTime-hard, even if the arity of EDB relations is bounded by two, rule bodies are connected and tree-shaped, and there are no constants.
This is already established in [