Riccardo Rosati.
In Proceedings of the 2007 International Workshop on Description Logic (DL 2007), CEUR Electronic Workshop Proceedings, 2007.
We study conjunctive query answering in the description logics of the EL family, and present the following results: (i) we define a technique for answering unions of conjunctive queries in EL (and in its extension ELH), based on a rewriting of the query in terms of a recursive Datalog query; (ii) the above technique allows us to prove that answering unions of conjunctive queries in EL and ELH is PTIME-complete with respect to knowledge base complexity (i.e., with respect to the size of the knowledge base) and is NP-complete with respect to combined complexity (i.e., with respect to the size of both the knowledge base and the query); (iii) conversely, we prove that answering conjunctive queries is undecidable in EL+ and EL++, two well-known extensions of EL.
@String{DL-07 = "Proceedings of the 2007 International Workshop on Description Logic (DL~2007)"}
@Inproceedings{Rosa07c,
author = "Riccardo Rosati",
title = "On conjunctive query answering in {EL}",
booktitle = DL-07,
publisher = "CEUR Electronic Workshop Proceedings",
year = 2007,
}