Proc. of the 18th Int. Workshop on Description Logics (DL 2005). Volume 147 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2005.
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.
@inproceedings{DL-2005, title = "Data Complexity of Query Answering in Description Logics", year = "2005", author = "Diego Calvanese and De Giacomo, Giuseppe and Domenico Lembo and Maurizio Lenzerini and Riccardo Rosati", booktitle = "Proc. of the 18th Int. Workshop on Description Logics (DL 2005)", volume = "147", publisher = "CEUR-WS.org", series = "CEUR Workshop Proceedings, https://ceur-ws.org/", }pdf url