Data complexity of query answering in Description Logics

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati.
In Proceedings of the 2005 Description Logic Workshop (DL 2005), 2005.

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.

Bibtex entry:

@String{DL-05 = "Proceedings of the 2005 Description Logic Workshop (DL~2005)"}

@Inproceedings{CDLLR05b,
author = "Diego Calvanese and De Giacomo, Giuseppe and Domenico Lembo and Maurizio Lenzerini and Riccardo Rosati",
title = "Data complexity of query answering in Description Logics",
booktitle = DL-05,
year = 2005,
}