Conjunctive queries for EL with role composition - Krötzsch, M; Rudolph, S (2007)
EL++ is a rather expressive description logic (DL) that still admits polynomial time inferencing for many reasoning tasks. Conjunctive queries are an important means for expressive querying of DL knowledge bases. We address the problem of computing conjunctive query entailment for EL ++ knowledge bases. As it turns out, querying unrestricted EL ++ is actually undecidable, but we identify restrictions under which query answering becomes decidable and even tractable.We give precise characterisations of schema, query, and combined complexity. To the best of our knowledge, the presented algorithm is the first to answer conjunctive queries in a DL that admits complex role inclusion axioms. © 2007 by Bozen-Bolzano University Press.