Data complexity of query answering in description logics

D Calvanese, G De Giacomo, D Lembo, M Lenzerini… - Artificial Intelligence, 2013 - Elsevier
Artificial Intelligence, 2013Elsevier
In this paper we study data complexity of answering conjunctive queries over description
logic (DL) knowledge bases constituted by a TBox and an ABox. In particular, we are
interested in characterizing the FOL-rewritability and the polynomial tractability boundaries
of conjunctive query answering, depending on the expressive power of the DL used to
express the knowledge base. FOL-rewritability means that query answering can be reduced
to evaluating queries over the database corresponding to the ABox. Since first-order queries …
In this paper we study data complexity of answering conjunctive queries over description logic (DL) knowledge bases constituted by a TBox and an ABox. In particular, we are interested in characterizing the FOL-rewritability and the polynomial tractability boundaries of conjunctive query answering, depending on the expressive power of the DL used to express the knowledge base. FOL-rewritability 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-rewritability is that, when query answering enjoys this property, we can take advantage of Relational Data Base Management System (RDBMS) 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 essentially the maximal logics allowing for 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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果