Query Inseparability by Games
Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2014
Abstract. We investigate conjunctive query inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental prob-lem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity re-sults ranging from P to EXPTIME and 2EXPTIME. We also employ our results to resolve two major open problems for OWL2QL by showing that TBox query in-separability and the membership problem for universal UCQ-solutions in knowl-edge exchange are both EXPTIME-complete for combined complexity.