Data Complexity of Query Answering in Description Logics

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/",
}