Ontology-Based Data Access with Closed Predicates is Inherently Intractable(Sometimes)

Lutz, Carsten; Seylan, Inanç; Wolter, Frank

Ontology-Based Data Access with Closed Predicates is Inherently Intractable(Sometimes)

Carsten Lutz, Inanç Seylan, Frank Wolter

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 1024-1029.

Abstract

When answering queries in the presence of ontologies, adopting the closed world assumption for some predicates easily results in intractability. We analyze this situation on the level of individual ontologies formulated in the description logics DL-Lite and EL and show that in all cases where answering CQs with (open and) closed predicates is tractable, it coincides with answering CQs with all predicates assumed open. In this sense, CQ answering with closed predicates in inherently intractable. Our analysis also yields a dichotomy between AC0 and coNP for CQ answering in DL-Lite and a dichotomy between PTime and coNP for EL. Interestingly, the situation is less dramatic in the more expressive description logic ELI, where we find ontologies for which CQ answering is in PTime, but does not coincide with CQ answering where all predicates are open.

Carsten Lutz, Inanç Seylan, and Frank Wolter. 2013. Ontology-Based Data Access with Closed Predicates is Inherently Intractable(Sometimes). In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 1024–1029. https://ijcai.org/proceedings/2013/156

@inproceedings{ijcai2013p156,
  title     = {Ontology-Based Data Access with Closed Predicates is Inherently Intractable(Sometimes)},
  author    = {Lutz, Carsten and Seylan, Inanç and Wolter, Frank},
  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     = {1024--1029},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/156},
}

TY  - CPAPER
TI  - Ontology-Based Data Access with Closed Predicates is Inherently Intractable(Sometimes)
AU  - Lutz, Carsten
AU  - Seylan, Inanç
AU  - Wolter, Frank
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  - 1024
EP  - 1029
UR  - https://ijcai.org/proceedings/2013/156
ER  -