Data complexity in the εL family of DLs

Adila Alfa Krisnadhi, Carsten Lutz

Research output: Contribution to journalConference articlepeer-review

9 Citations (Scopus)


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 Dn-1 implies A, T |= Di(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. ELIf ) 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 Gi = (Ni, T, Pi, Si), 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 ra | a ∈ T} [ {rA1..... rAn rA | A → A1 · · ·An ∈ P1 [ P2}. It is not too difficult to see that L(G1)\L(G2) ≠ θ iff the conjunctive query S1(u, v)^ S2(u, v) is matched by the ABox {T(a)} and TBox T .

Original languageEnglish
Pages (from-to)88-99
Number of pages12
JournalCEUR Workshop Proceedings
Publication statusPublished - 2007
Event20th International Workshop on Description Logics, DL 2007 - Brixen/Bressanone, Italy
Duration: 8 Jun 200710 Jun 2007


Dive into the research topics of 'Data complexity in the εL family of DLs'. Together they form a unique fingerprint.

Cite this