AAAI Publications, Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
Query Inseparability for Description Logic Knowledge Bases
Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev

Last modified: 2014-05-04


We investigate conjunctive query inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL 2 QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to EXPTIME and 2EXPTIME. We also resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME-complete for combined complexity.


Query Answering; Description Logics and Ontologies; Computational Complexity

Full Text: PDF