Skip to main content

Games for query inseparability of description logic knowledge bases

Botoeva, Elena, Kontchakov, Roman, Ryzhikov, Vladislav, Wolter, Frank, Zakharyaschev, Michael (2016) Games for query inseparability of description logic knowledge bases. Artificial Intelligence, 234 . pp. 78-119. ISSN 0004-3702. (doi:10.1016/j.artint.2016.01.010) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:90810)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. (Contact us about this Publication)
Official URL
https://doi.org/10.1016/j.artint.2016.01.010

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-ALCHJ, 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
DOI/Identification number: 10.1016/j.artint.2016.01.010
Uncontrolled keywords: Description logic; Knowledge base; Conjunctive query; Query inseparability; Games on graphs; Computational complexity
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Amy Boaler
Date Deposited: 12 Oct 2021 09:05 UTC
Last Modified: 13 Oct 2021 10:35 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/90810 (The current URI for this page, for reference purposes)
  • Depositors only (login required):