EQL-Lite: Effective First-Order Query Processing in Description Logics

Abstract

Querying Description Logic knowledge bases has received great attention in the last years. In such a problem, the need of coping with incomplete information is the distinguishing feature with respect to querying databases. Due to this feature, we have to deal with two conflicting needs: on the one hand, we would like to query the knowledge base with sophisticated mechanisms provided by full first-order logic (FOL); on the other hand, the presence of incomplete information makes query answering a much more difficult task than in databases. In this paper we advocate the use of a nonmonotonic epistemic FOL query language as a means for expressing sophisticated queries over Description Logic knowledge bases. We show that through a controlled use of the epistemic operator, resulting in the language called EQL-Lite, we are able to formulate full FOL queries over Description Logic knowledge bases, while keeping computational complexity of query answering under control. In particular, we show that EQL-Lite queries over DL-Lite knowledge bases are FOL reducible (i.e., compilable into SQL) and hence can be answered in LOGSPACE through standard database technologies.