Data Complexity of Query Answering in Description Logics

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati

Proc. of the 18th Int. Workshop on Description Logics (DL 2005). Volume 147 of CEUR Workshop Proceedings, http://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",
   series = "CEUR Workshop Proceedings, http://ceur-ws.org/",
}
pdf url