First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics
This work addresses the complexity of query answering for database and knowledge representation researchers, particularly in the context of description logics.
This paper investigates the FO-rewritability of conjunctive queries in description logics between EL and Horn-SHIF, along with query containment. It provides characterizations and establishes complexity results ranging from ExpTime to 2ExpTime.
We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizations, we establish complexity results ranging from ExpTime via NExpTime to 2ExpTime, pointing out several interesting effects. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.