Tractable query answering and rewriting under description logic constraints

Answering queries over an incomplete database w.r.t. a set of constraints is an important computational task with applications in fields as diverse as information integration and metadata management in the semantic Web. Description Logics (DLs) are constraint languages that have been extensively studied with the goal of providing useful modeling constructs while keeping the query answering problem decidable. For many DLs, query answering under constraints can be solved via query rewriting: given a conjunctive query Q   and a set of DL constraints TT, the query Q   can be transformed into a datalog query QTQT that takes into account the semantic consequences of TT; then, to obtain answers to Q   w.r.t. TT and some (arbitrary) database instance AA, one can simply evaluate QTQT over AA using existing (deductive) database technology, without taking TT into account. In this paper, we present a novel query rewriting algorithm that handles constraints modeled in the DL ELHIO¬ELHIO¬ and use it to show that answering conjunctive queries in this setting is PTime-complete w.r.t. data complexity. Our algorithm deals with various description logics of the ELEL and DL-Lite families and is worst-case optimal w.r.t. data complexity for all of them.