Data complexity in the εL family of DLs

The results of our investigation are summarized in Table 1, and in all cases they apply both to instance checking and conjunctive query entailment. The coNP upper bounds are a consequence of the results in [9]. When the UNA is not explicitly mentioned, the results hold both with and without UNA. We point out two interesting issues. First, for all of the considered extensions we were able to show tractability regarding data complexity if and only if the logic is convex regarding instances, i.e., A, T |= C(a) with C = D0 t · · · U D_n-1 implies A, T |= D_i(a) for some i < n. It would be interesting to capture this phenomenon in a general result. And second, it is interesting to point out that subtle differences such as the UNA or local versus global functionality (for the latter, see EL^(≤1r) vs. ELI^f ) can have an impact on tractability. As future work, it would be interesting extend our upper bound by including more operators from the tractable description logic EL⁺⁺ as proposed in [1]. For a start, it is not hard to show that conjunctive query entailment in full EL⁺⁺ is undecidable due to the presence of role inclusions r1 ± r2 s. In the following, we briefly sketch the proof, which is by reduction of the problem of deciding whether the intersection of two languages defined by given context-free grammars G_i = (N_i, T, P_i, S_i), i ∈ {1, 2}, is empty. We assume w.l.o.g. that the set of non-terminals N1 and N2 are disjoint. Then define a TBox T := {T v r_a | a ∈ T} [ {rA₁..... rA_n r_A | A → A1 · · ·A_n ∈ P₁ [ P₂}. It is not too difficult to see that L(G₁)\L(G₂) ≠ θ iff the conjunctive query S1(u, v)^ S2(u, v) is matched by the ABox {T(a)} and TBox T .