Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access

Bienvenu, Meghyn; Rosati, Riccardo

Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 775-780.

Abstract

A robust system for ontology-based data access should provide meaningful answers to queries even when the data conflicts with the ontology. This can be accomplished by adopting an inconsistency-tolerant semantics, with the consistent query answering (CQA) semantics being the most prominent example. Unfortunately, query answering under the CQA semantics has been shown to be computationally intractable, even when extremely simple ontology languages are considered. In this paper, we address this problem by proposing two new families of inconsistency-tolerant semantics which approximate the CQA semantics from above and from below and converge to it in the limit. We study the data complexity of conjunctive query answering under these new semantics, and show a general tractability result for all known first-order rewritable ontology languages. We also analyze the combined complexity of query answering for ontology languages of the DL-Lite family.

Meghyn Bienvenu, and Riccardo Rosati. 2013. Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 775–780. https://ijcai.org/proceedings/2013/121

@inproceedings{ijcai2013p121,
  title     = {Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access},
  author    = {Bienvenu, Meghyn and Rosati, Riccardo},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {775--780},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/121},
}

TY  - CPAPER
TI  - Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access
AU  - Bienvenu, Meghyn
AU  - Rosati, Riccardo
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 775
EP  - 780
UR  - https://ijcai.org/proceedings/2013/121
ER  -