Games for query inseparability of description logic knowledge bases

Botoeva, E, Kontchakov, R, Ryzhikov, V, Wolter, F and Zakharyaschev, M
(2016) Games for query inseparability of description logic knowledge bases. Artificial Intelligence, 234. pp. 78-119.

[img] Text
aij-final.pdf - Author Accepted Manuscript

Download (578kB)


We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature - a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.

Item Type: Article
Uncontrolled Keywords: Description logic, Knowledge base, Conjunctive query, Query inseparability, Games on graphs, Computational complexity
Depositing User: Symplectic Admin
Date Deposited: 07 Jul 2016 10:24
Last Modified: 19 Jan 2023 07:36
DOI: 10.1016/j.artint.2016.01.010
Related URLs: