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.

Text aij-final.pdf - Author Accepted Manuscript Download (578kB)

Abstract

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001404