Data complexity of query answering in description logics

TLDR

FOL‑reducibility allows conjunctive query answering to be reformulated as SQL queries over the ABox, enabling the use of standard database management systems. The paper investigates the boundaries of FOL‑reducibility and polynomial tractability for conjunctive query answering across different Description Logics. The authors analyze data complexity by examining conjunctive query answering over DL knowledge bases composed of an ABox and a TBox, focusing on how the expressive power of the DL influences FOL‑reducibility and tractability. Their analysis shows that DL‑Lite is the most expressive family that still permits conjunctive query answering through standard database technology, making it the first DL designed for efficient query answering over very large ABoxes.

Abstract

In this paper we study data complexity of answering conjunctive queries over Description Logic knowledge bases constituted by an ABox and a TBox. In particular, we are interested in characterizing the FOL-reducibility and the polynomial tractability boundaries of conjunctive query answering, depending on the expressive power of the Description Logic used to specify the knowledge base. FOL-reducibility means that query answering can be reduced to evaluating queries over the database corresponding to the ABox. Since first-order queries can be expressed in SQL, the importance of FOL-reducibility is that, when query answering enjoys this property, we can take advantage of Data Base Management System (DBMS) techniques for both representing data, i.e., ABox assertions, and answering queries via reformulation into SQL. What emerges from our complexity analysis is that the Description Logics of the DL-Lite family are the maximal logics allowing conjunctive query answering through standard database technology. In this sense, they are the first Description Logics specifically tailored for effective query answering over very large ABoxes.