Data Complexity of Query Answering in Description Logics (Extended Abstract)

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

Data Complexity of Query Answering in Description Logics (Extended Abstract)

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

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Journal Track. Pages 4163-4166.

Abstract

We study the data complexity of answering conjunctive queries over Description Logic knowledge bases constituted by a TBox and an ABox. In particular, we are interested in characterizing the FO- rewritability and the polynomial tractability boundaries of conjunctive query answering, depending on the expressive power of the DL used to express the knowledge base. 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.

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2015. Data Complexity of Query Answering in Description Logics (Extended Abstract). In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 4163–4166. https://ijcai.org/proceedings/2015/588

@inproceedings{ijcai2015p588,
  title     = {Data Complexity of Query Answering in Description Logics (Extended Abstract)},
  author    = {Calvanese, Diego and De Giacomo, Giuseppe and Lembo, Domenico and Lenzerini, Maurizio and Rosati, Riccardo},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {4163--4166},
  year      = {2015},
  month     = {7},
  note      = {Journal Track},
  url       = {https://ijcai.org/proceedings/2015/588},
}

TY  - CPAPER
TI  - Data Complexity of Query Answering in Description Logics (Extended Abstract)
AU  - Calvanese, Diego
AU  - De Giacomo, Giuseppe
AU  - Lembo, Domenico
AU  - Lenzerini, Maurizio
AU  - Rosati, Riccardo
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 4163
EP  - 4166
UR  - https://ijcai.org/proceedings/2015/588
ER  -