Abstract
In this paper we study data complexity of answering conjunctive queries over DL knowledge bases constituted by an ABox and a TBox. In particular, we characterize the LogSpace boundary (over the data) of the problem. This boundary is particularly meaningful because, when we go above it, query answering is not expressible as a first-order logic formula (and hence an SQL query) over the data. Within the LogSpace boundary we essentially find DL-Lite, a simple DL that is rich enough to express the core of UML class diagrams. The second contribution of the paper is to establish coNP-hardness of query answering with respect to data complexity for various cases of surprisingly simple DLs.