Rewriting Conjunctive Queries under Description Logic Constraints
Héctor Pérez-Urbina · 2008
Abstract. We consider the problems of conjunctive query answering and rewriting under Description Logic constraints. We present a query rewriting algorithm for ELHI knowledge bases, and use it to show that query answering in this setting is PTime-complete w.r.t. data complexity. We show that our algorithm is worst-case optimal for languages with data complexity of query answering ranging from LogSpace to PTimecomplete. 1